C. Tree Infection

https://codeforces.com/problemset/problem/1665/C

题目

解析

很显然，树的节点感染只会在兄弟节点之间，每层独立的兄弟节点都得感染至少一个，然后让他自由扩展（时间差），那么很显然第一遍就是每层都得感染。感染的次序就是按照兄弟节点的数量降序，并且要加上1的单独节点。然后如果vis-(i-1)比当前层数少，说明第一遍无法磨灭全部，那么就把差值存到大根堆中。然后通过每次额外把最大的一个值减一使得时间最小，设置结束条件为spread>=pq.top()就是自由扩散的值已经够把所有的节点覆盖的时候。

代码

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#define IOS ios::sync_with_stdio(false), cin.tie(0) ,cout.tie(0)
using namespace std;
#define int long long
const int N = 2e5 + 10;

struct ele
{
	int id, val;
}eles[N];
bool cmp(ele a, ele b) { return a.val > b.val; }
signed main()
{
	IOS;
	int t; cin >> t;
	while (t--)
	{
		int n; cin >> n;
		int vis = 0;
		for (int i = 1; i <= n; i++)
		{
			eles[i].id = i;
			eles[i].val = 0;
		}
		for (int i = 1; i < n; i++)
		{
			int x; cin >> x;
			eles[x].val++;
			if (eles[x].val == 1)vis++;
		}
		sort(eles + 1, eles + 1 + n, cmp);
		eles[vis + 1].val = 1;
		vis++;
		int ans = vis;
		priority_queue<int>pq;
		for (int i = 1; i <= vis; i++)
		{
			if (eles[i].val > vis - i + 1)
			{
				pq.push(eles[i].val - vis + i - 1);
			}
		}
		int spread = 0;//每一层平均减去的值
		while (!pq.empty() and spread < pq.top())//每层平均下降，那么相当于底线水平上升
		{
			int x = pq.top() - 1;
			pq.pop(); pq.push(x);
			spread++;
		}
		ans += spread;
		cout << ans  << '\n';
	}

	return 0;
}