Educational Codeforces Round 136 (Rated for Div. 2) D - Reset K Edges

题目来源：Educational Codeforces Round 136 (Rated for Div. 2) D

题目链接：Problem - D - Codeforces

题意

给定一棵以1为根、大小为n的树，每次操作可以将一棵子树接到根节点。求进行最多K次操作时，树高度的最小值。

数据范围：$n \ge 2$, $\sum{n} \le 2·10^5$. 

思路：二分答案

考虑二分答案。

当树高度确定时，就可以贪心地进行操作：记期望的树高度为x，此处我们把每个结点的高度理解成，以该结点为根的子树的高度，那么就可以从叶子结点往上遍历，当此时结点的高度为x-1，其父亲不是根节点，自身也不是根节点时，就需要进行一次操作，将其接到根节点处。这样进行的操作数是最少的，判断下此时至少需要进行的操作数跟K的大小关系来变化二分的区间。

从下往上贪心的正确性：当此时结点的高度为x-1，其父亲不是根节点，自身也不是根节点时，是必须进行一次操作的；而提前进行操作，必定不会使最终的操作数减少。因此这样贪心是正确的。

时间复杂度：O(nlogn).

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

const int N = 200010;

int n, k, p[N];
vector<int> g[N];

int dfs(int u, int x, int& cnt)
{
    int dep = 0;
    for(auto v : g[u]) {
        dep = max(dep, dfs(v, x, cnt) + 1);
    }
    if(dep == x - 1 && p[u] != 1 && u != 1) {
        ++ cnt;
        return -1;
    }
    return dep;
}

void solve()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) g[i].clear(), g[i].shrink_to_fit();
    for(int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        p[i] = x, g[x].push_back(i);
    }

    int l = 1, r = n - 1;
    while(l <= r) {
        int mid = l + r >> 1, cnt = 0;
        dfs(1, mid, cnt);
        if(cnt <= k) r = mid - 1;
        else l = mid + 1;
    }
    cout << l << endl;
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int test;
    cin >> test;
    while(test--) solve();

    return 0;
}