Tree Infection(1600 二分)

传送门

一、题意：

在一棵树上进行1s内进行两种操作：

1、Spreading：对于每个节点，如果有叶子节点被感染了，可以选择另外一个没有被感染过的叶子节点进行感染

2、Injection：可以选择任意一个健康节点进行感染

问将所有节点感染花费的最少时间？

二、思路：

二分，优先叶子节点多的块进行Injection，剩下的能否在mid - 1时间内感染完成

三、代码：

 1 #include 
 2 using namespace std;
 3 
 4 const int N = 2e5 + 10;
 5 int n, x, cnt, a[N];
 6 vector<int> g[N];
 7 
 8 bool check(int x){
 9     int rest = 0;
10     for(int i = 1, j = x - 1; i <= cnt; i++, j--){
11         rest += max(0, a[i] - j);
12     }
13     return x - cnt >= rest;
14 }
15 
16 void accept() {
17     cin >> n;
18     for(int i = 1; i <= n; ++i) g[i].clear();
19     for(int i = 2; i <= n; ++i) {
20         cin >> x;
21         g[x].push_back(x);
22     }
23 
24     cnt = 1, a[1] = 0;
25     for(int i = 1; i <= n; ++i) {
26         if(g[i].size()) a[++cnt] = g[i].size() - 1;
27     }
28     sort(a + 1, a + 1 + cnt, greater<int>());
29 
30     int l = cnt, r = n;
31     while(l < r) {
32         int mid = l + r >> 1;
33         if(check(mid)) r = mid;
34         else l = mid + 1;
35     }
36 
37     cout << l << "\n";
38 }
39 
40 signed main() {
41     ios::sync_with_stdio(false);
42     cin.tie(nullptr);
43     int t;
44     cin >> t;
45     for(int i = 0; i < t; ++i) accept();
46     return 0;
47 }