C.TreeInfection(二分)-创新互联

Problem - 1665C - Codeforces

主要从事网页设计、PC网站建设（电脑版网站建设）、wap网站建设（手机版网站建设）、成都响应式网站建设、程序开发、微网站、微信平台小程序开发等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了丰富的成都网站设计、成都网站制作、网络营销经验，集策划、开发、设计、营销、管理等多方位专业化运作于一体，具备承接不同规模与类型的建设项目的能力。

一棵树是一个没有循环的连接图。一棵有根的树有一个特殊的顶点，叫做根。一个顶点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#include
#include#include#include#include#includeusing namespace std;
#define int long long
//1 1 3 3 3
int son[200050];
int cnt;
vectorv[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<>t;
	while(t--)
	{
		solve();
	}
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享文章：C.TreeInfection(二分)-创新互联
新闻来源：http://scyanting.com/article/dposjg.html

C.TreeInfection(二分)-创新互联

其他资讯