C. Tree Infection(二分)

Problem - 1665C - Codeforces

 

一棵树是一个没有循环的连接图。一棵有根的树有一个特殊的顶点，叫做根。一个顶点v（不同于根）的父顶点是指从根到顶点v的最短路径上的前一个顶点。

给你一棵有n个顶点的有根树。顶点1是根。最初，所有顶点都是健康的。

每一秒钟你做两个操作，传播操作，之后是注入操作。

传播：对于每个顶点，如果至少有一个v的孩子被感染，你可以通过感染你选择的v的最多一个其他孩子来传播疾病。
注入：你可以选择任何健康的顶点并感染它。
这个过程每秒重复一次，直到整个树被感染。你需要找到感染整棵树所需的最小秒数。

输入
输入由多个测试案例组成。第一行包含一个整数t（1≤t≤104）--测试案例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数n（2≤n≤2⋅105）--给定树中顶点的数量。

每个测试用例的第二行包含n-1个整数p2,p3,...,pn（1≤pi≤n），其中pi是树中第i个顶点的祖先。

可以保证给定的图是一棵树。

保证所有测试案例的n之和不超过2⋅105。

输出
对于每个测试案例，你应该输出一个整数--感染整个树所需的最小秒数。

例子
inputCopy
5
7
1 1 1 2 2 4
5
5 5 1 4
2
1
3
3 1
6
1 1 1 1 1
输出拷贝
4
4
2
3
4

题解:
首先我们要明确:

只有同一个父节点的字节的才可以通过传播感染,子节点是无法传播到父节点的,所以父节点只能通过注入感染

但是还有一个特例,1是没有父节点的,所以他只能通过注入感染

所以初始cnt = 0

对于传播感染,前提是父节点已经感染,

然后就是二分

最先开始传播感染的应该是字结点最多的,所以我们要排一下序

每次check,x秒内是否可以全部感染完即可

剩下一些细节在代码中有注释

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define int long long
//1 1 3 3 3
int son[200050];
int cnt;
vector<int> v[200050];
int check(int x)
{
	int ans = 0;
	int k = 0;
	for(int i = 1,j = x- 1;i <= cnt;j --,i++)//被传播感染的结点,前提是有一个已经传染的父节点,所以先减1
	{
		ans += max(k,son[i] - j);
	}
	return x - cnt>= ans;//先注入感染的在这里有体现,减了cnt个注入感染的
}
void solve()
{
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	v[i].clear();
	for(int i = 2;i <= n;i++)
	{
		int x;
		cin >> x;
		v[x].push_back(i);
	}
	cnt = 1;//由于1没有父节点,所以1肯定是要通过方式2感染的 
	son[1] = 0;//单纯清空数组,无特殊含义 
	for(int i = 1;i <= n;i++)
	{
		if(v[i].size())
		{
			son[++cnt] = v[i].size() - 1;//要开始传播感染,首先要注入感染一个
		}
	} 
	sort(son+1,son+1+cnt,greater<>());
	int l = cnt,r = n;
	while(l <= r)
	{
		int mid = (l+r)/2;
		if(check(mid))
		{
			r = mid - 1;
		}
		else{
			l = mid + 1;
		}
		
	}
	cout<<l<<"\n";
}
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve();
	}
}