C. Tree Infection

本文主要是介绍C. Tree Infection，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：先处理出每个结点有多少个子节点，然后存到数组中，然后用二分时间。

首先Injection一定用于优先感染兄弟结点比较多的结点,这样可以充分利用Spreading,我们可以结点按照兄弟的数量排序,然后优先感染兄弟多的结点.这样我们就知道了,第一秒被Injection的结点剩下的时间里可以被Spreading mid - 1个兄弟,第二秒可以被Injection的结点可以被Spreading mid - 2个兄弟,所以我们扫描一遍就可以知道还剩下多少个兄弟结点还没被感染,判断能否用剩下的Injection的操作将这些结点感染即可.

代码：

vector<int>a[200010];
int n, cnt, bro[200010];bool check(int mid){int remain = 0;for(int i = 1, j = mid;i <= cnt; i ++, j --){remain += max(0ll, bro[i] - j);}return mid - cnt >= remain;
}void solve(){cin >> n;for(int i = 1;i <= n;i ++)a[i].clear();for(int i = 2;i <= n;i ++){int x;cin >> x;a[x].push_back(i);}cnt = 1;bro[1] = 1;for(int i = 1;i <= n;i ++){if(a[i].size()){bro[ ++ cnt] = a[i].size();}}sort(bro + 1,bro + cnt + 1,greater<int>());int l = cnt - 1, r = n + 1;while(l + 1 != r){int mid = l + r >> 1;if(check(mid))r = mid;else l = mid;}cout << r << endl;
}

这篇关于C. Tree Infection的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---