C.TreeInfection(二分)-創(chuàng)新互聯(lián)

Problem - 1665C - Codeforces

主要從事網(wǎng)頁設計、PC網(wǎng)站建設（電腦版網(wǎng)站建設）、wap網(wǎng)站建設（手機版網(wǎng)站建設）、成都響應式網(wǎng)站建設、程序開發(fā)、微網(wǎng)站、微信平臺小程序開發(fā)等，憑借多年來在互聯(lián)網(wǎng)的打拼，我們在互聯(lián)網(wǎng)網(wǎng)站建設行業(yè)積累了豐富的成都網(wǎng)站設計、成都網(wǎng)站制作、網(wǎng)絡營銷經(jīng)驗，集策劃、開發(fā)、設計、營銷、管理等多方位專業(yè)化運作于一體，具備承接不同規(guī)模與類型的建設項目的能力。

一棵樹是一個沒有循環(huán)的連接圖。一棵有根的樹有一個特殊的頂點，叫做根。一個頂點v（不同于根）的父頂點是指從根到頂點v的最短路徑上的前一個頂點。

給你一棵有n個頂點的有根樹。頂點1是根。最初，所有頂點都是健康的。

每一秒鐘你做兩個操作，傳播操作，之后是注入操作。

傳播：對于每個頂點，如果至少有一個v的孩子被感染，你可以通過感染你選擇的v的最多一個其他孩子來傳播疾病。
注入：你可以選擇任何健康的頂點并感染它。
這個過程每秒重復一次，直到整個樹被感染。你需要找到感染整棵樹所需的最小秒數(shù)。

輸入
輸入由多個測試案例組成。第一行包含一個整數(shù)t（1≤t≤104）--測試案例的數(shù)量。測試用例的描述如下。

每個測試用例的第一行包含一個整數(shù)n（2≤n≤2?105）--給定樹中頂點的數(shù)量。

每個測試用例的第二行包含n-1個整數(shù)p2,p3,...,pn（1≤pi≤n），其中pi是樹中第i個頂點的祖先。

可以保證給定的圖是一棵樹。

保證所有測試案例的n之和不超過2?105。

輸出
對于每個測試案例，你應該輸出一個整數(shù)--感染整個樹所需的最小秒數(shù)。

例子
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

題解:
首先我們要明確:

只有同一個父節(jié)點的字節(jié)的才可以通過傳播感染,子節(jié)點是無法傳播到父節(jié)點的,所以父節(jié)點只能通過注入感染

但是還有一個特例,1是沒有父節(jié)點的,所以他只能通過注入感染

所以初始cnt = 0

對于傳播感染,前提是父節(jié)點已經(jīng)感染,

然后就是二分

最先開始傳播感染的應該是字結點最多的,所以我們要排一下序

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

剩下一些細節(jié)在代碼中有注釋

#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++)//被傳播感染的結點,前提是有一個已經(jīng)傳染的父節(jié)點,所以先減1
	{
		ans += max(k,son[i] - j);
	}
	return x - cnt>= ans;//先注入感染的在這里有體現(xiàn),減了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沒有父節(jié)點,所以1肯定是要通過方式2感染的 
	son[1] = 0;//單純清空數(shù)組,無特殊含義 
	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();
	}
}

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

分享文章：C.TreeInfection(二分)-創(chuàng)新互聯(lián)
標題來源：http://muchs.cn/article26/dposjg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供自適應網(wǎng)站、網(wǎng)站內鏈、面包屑導航、網(wǎng)頁設計公司、網(wǎng)站設計公司、做網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內容