题目链接: 点击跳转

题意: 给你一棵树，每次你可以依次进行以下操作，1.对于一个节点，如果该节点有至少一个子树被涂色(可以理解为图着色,原译不是涂色)了，那么你可以任选他的子树上的另一个节点使其被传染(可以对多个节点操作，但每个节点的子树在一次操作只能传染一次)，2.任选一个节点，使其被涂色(可以选1中操作过的子树中的节点)，问最少几次操作能使整棵树都被涂色。

思路: 开始想，从大的数量开始涂色，然后每棵更小的子树均可以对该子树提供传染的机会，但是这样子求出的值并不是最小的。
错误代码:

#include<bits/stdc++.h>
#include <ostream>

using namespace std;
typedef long long ll;
#define endl '\n'
typedef pair<int, int> PII;
#define debug() cout.flush()
#define for0(i, a) for (int i = 0; i < a; ++i)
#define REP(i, a, b)  for (int i = a; i < b; ++i)
#define FOR(i, a, b)  for (int i = a; i <= b; ++i)
#define REPC(i, a, b, c)  for (ll i = a; i < b && i < c; ++i)
#define RREP(i, a, b) for (int i = a; i >= b; --i)
const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 5e3;

inline void init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int n, sum[MAXN];

inline void solve() {
    for (int i = 0; i <= n + 200; i++) sum[i] = 0;
    for (int i = 2; i <= n; i++) {
        int a;
        cin >> a;
        sum[a]++;
    }
    vector<ll>v;
    v.clear();
    ll res = 1;
    for (int i = 1; i <= n; i++) {
        if (sum[i]) {
            if (sum[i] > 1)
                v.push_back(sum[i]);
            else res++;
        }
    }
    sort(v.begin(), v.end());
    for (auto i : v) {
        res += max(0ll, (i - res) / 2) + 1;
    }
    cout << res << endl;
}

signed main() {
    init();
    int _;
    cin >> _;
    while (_--) {
        cin >> n;
        solve();
//        debug();
    }
    return 0;
}

错误样例:

1 
21 
1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2

从错误样例能看出，两棵子树极大，会导致直接分配上不是最优
题目总的数据量为2e5，可以通过模拟染色的方式来进行操作，每次对剩下子树最多的进行操作2，同时操作1同时对所有子树进行。
要怎么维护呢，可以在操作前，根据子树的大小，从1到cnt(根节点数量)依次减去1-cnt,然后将减去后的结果放入优先队列，每次对堆顶减一，同时记录操作次数，当堆顶元素小于等于操作次数时，那么就说明全树都完成了染色操作，结束即可。

代码如下:

#include<bits/stdc++.h>
#include <ostream>

using namespace std;
typedef long long ll;
#define endl '\n'
typedef pair<int, int> PII;
#define debug() cout.flush()
#define for0(i, a) for (int i = 0; i < a; ++i)
#define REP(i, a, b)  for (int i = a; i < b; ++i)
#define FOR(i, a, b)  for (int i = a; i <= b; ++i)
#define REPC(i, a, b, c)  for (ll i = a; i < b && i < c; ++i)
#define RREP(i, a, b) for (int i = a; i >= b; --i)
const ll MOD = 1e9 + 7;
const ll mod = 998244353;
const int INF = 0x3f3f3f3f;
const int MAXN = 5e5 + 5e3;

inline void init() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int n, sum[MAXN];

inline void solve() {
    for (int i = 0; i <= n + 200; i++) sum[i] = 0;
    for (int i = 2; i <= n; i++) {
        int a;
        cin >> a;
        sum[a]++;
    }
    vector<ll>v;
    v.clear();
    ll res = 0;
    v.push_back(1);
    for (int i = 1; i <= n; i++) {
        if (sum[i]) {
            v.push_back(sum[i]);
        }
    }
    sort(v.begin(), v.end());
    res = v.size();
    priority_queue<ll>q;
    for (int i = 0; i < res; i++) {
        v[i] -= i + 1;
        if (v[i]) q.push(v[i]);
    }
    int cnt = 0;
    while (!q.empty() && q.top() > cnt) {
        ll tmp = q.top();
        q.pop();
        q.push(tmp - 1);
        cnt++;
    }
    cout << res + cnt << endl;
}

signed main() {
    init();
    int _;
    cin >> _;
    while (_--) {
        cin >> n;
        solve();
//        debug();
    }
    return 0;
}