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

Problem - 1665C - Codeforces

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

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

給你一棵有n個(gè)頂點(diǎn)的有根樹。頂點(diǎn)1是根。最初，所有頂點(diǎn)都是健康的。

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

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

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

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

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

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

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

輸出
對(duì)于每個(gè)測試案例，你應(yīng)該輸出一個(gè)整數(shù)--感染整個(gè)樹所需的最小秒數(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

題解:
首先我們要明確:

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

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

所以初始cnt = 0

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

然后就是二分

最先開始傳播感染的應(yīng)該是字結(jié)點(diǎn)最多的,所以我們要排一下序

每次check,x秒內(nèi)是否可以全部感染完即可

剩下一些細(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++)//被傳播感染的結(jié)點(diǎn),前提是有一個(gè)已經(jīng)傳染的父節(jié)點(diǎn),所以先減1
	{
		ans += max(k,son[i] - j);
	}
	return x - cnt>= ans;//先注入感染的在這里有體現(xiàn),減了cnt個(gè)注入感染的
}
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é)點(diǎn),所以1肯定是要通過方式2感染的 
	son[1] = 0;//單純清空數(shù)組,無特殊含義 
	for(int i = 1;i<= n;i++)
	{
		if(v[i].size())
		{
			son[++cnt] = v[i].size() - 1;//要開始傳播感染,首先要注入感染一個(gè)
		}
	} 
	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)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

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

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

廣告

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

成都定制網(wǎng)站建設(shè)