CF#781(Div.2),(C)TreeInfection

Problem - C - Codeforces

 

 

 

 

Example

input

571 1 1 2 2 455 5 1 42133 161 1 1 1 1

output

44234

 

 

题意

n个点组成一个树, 1作为根节点, 输入第2~n个数的父节点序号, 问最少几次感染操作会使得整棵树全被感染, 每次两种感染操作都会进行1. 感染: 单独感染一个点  2.扩散: 如果某一父节点的孩子有感染的, 则在此父节点下的一个孩子也可以被感染

题解

开始想的按孩子数多少从小到大排序, 依次操作 --> 不行, 因为若出现多个父节点的孩子数一样且很多的时候, 不可以挨个依次操作, 每个孩子堆 都得先感染一个使得操作2不被浪费

正解: 也是先按孩子数从小到大排序, 孩子数q[i]减去每个孩子堆只会先单独感染一个点到最后感染的个数, 即q[i]-i-2,  2=根节点1感染一次+i的孩子第一次感染, 最后放到堆里, 每次最大的取出, 最大的-1再压进去, 直到小于等于cnt

贴代码

#include <bits/stdc++.h>using namespace std;typedef long long LL;typedef pair<double,double> PII;const int N = 2e5+10;int mp[N], sum[N];int main(){    int t;    cin >> t;    while(t --)    {        int n, times=1;        cin>>n;        for(int i = 0; i <= n; i ++) mp[i] = 0, sum[i] = 0;        for(int i = 1; i < n; i ++)        {            int a;            cin >> a;            if(mp[a]==0)times++;            mp[a]++;//i的孩子数        }        vector<int> q;        for(int i = 1; i <= n; i ++)            if(mp[i])                q.push_back(mp[i]);                        sort(q.begin(), q.end());                priority_queue<int> sum;        for(int i = 0; i < q.size(); i ++)            if(q[i]-1-i > 0)                sum.push(q[i]-2-i);                int cnt = 0;        while(sum.size())        {            int tt = sum.top();            sum.pop();            if(tt>cnt)            {                sum.push(tt-1);                cnt ++;            }            else                break;        }        cout << times+cnt<<endl;    }        return 0;}