C. Tree infection (simulation + greed)

Codeforces Round #781 (Div. 2)

Solution

Be careful ： It's infection before injection .
greedy ： First, inject the subtree with the most child nodes , Until all subtrees with child nodes are injected , Reinjection 1 Root node No （ Actually 1 The root node can be understood as a subtree with a child node ,0 It's the parent node ,0 No need to be infected and injected ）. After all subtrees have infected nodes , Inject the largest number of child nodes at a time , Then all subtrees infect another node . Keep simulating this process , Until all nodes are infected .

Obvious , Every sub tree needs an injection . Count the number of child nodes of all nodes $a[i]$（ The root node 1 It's got to be included , Equivalent to a subtree with a child node , Because of the node 1 Also inject alone ）, Then start with the tree with the most child nodes , Inject... In turn . After all subtrees have infected child nodes , obviously , For the first $i$ （ Subscript from 0 Start ） The number of remaining nodes in the tree is $a[i]-(n-i)$. here , Simulate the remaining child nodes .

Code

const int N = 2e5 + 6;
int a[N];
int main()
{
    
	IOS;
	int T; cin >> T;
	while (T--)
	{
    
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
			a[i] = 0;
		for (int i = 2, x; i <= n; i++)
			cin >> x, a[x]++;
		
		vector<int> v;
		v.emplace_back(1);
		for (int i = 1; i <= n; i++)
			if (a[i]) v.emplace_back(a[i]);

		sort(all(v), greater<int>());
		int ans = sz(v);
		for (int i = 0, len = sz(v); i < len; i++)
			v[i] -= len - i;
		while (!v.empty() && v.back() <= 0) v.pop_back();

		while (!v.empty())
		{
    
			sort(all(v), greater<int>());
			int last = 0;
			for (int i = 1, len = sz(v); i < len; i++)
				if (v[i] == v[i - 1])
					last = i;
				else break;
			v[last]--;
			ans++;
			for (int i = 0, len = sz(v); i < len; i++)
				v[i]--;
			while (!v.empty() && v.back() <= 0) v.pop_back();
		}

		cout << ans << endl;
		//cout << "--------------------\n";
	}

	return 0;
}