CF1739D Reset K Edges【树重构 + 最值边界二分】

题目链接

Educational Codeforces Round 136 (Rated for Div. 2), Problem D
1739D Reset K Edges

题目大意

给定一棵有根树，节点数为 $n$，编号 $1,2,\dots ,n$，根节点编号为 $1$。题目保证 $i$ 节点的父节点编号 $p_i<i$。
给定 $k$ 轮树重构操作，每轮操作可选择一节点 $u$ 断开与父节点 $v$ 连接，点并将 $u$ 与其子树一并连接到根节点 $1$ 上，即删边 $(v,u)$，增边 $(1,u)$。
求最终能获得树的最小高度值（根节点高度记为 $0$）。

解法

最值边界二分

较为典型的最大值最小化问题，只是操作对象变为了树的重构。

由于约束较少，优化方向发散，可以通过二分法夹逼树重构后合法的高度值，来获得最小高度值：

• 如测试高度 mid 可通过 $k$ 轮树重构操作达到，则更新最小高度 ans 答案，高度上界 biggestHight 收紧；
• 如测试高度 mid 不能通过 $k$ 轮树重构操作达到，则高度下界 smallestHight 收紧。

int smallestHight = 1, biggestHight = n-1;
int mid;
int ans = n-1;

while (smallestHight <= biggestHight){
    mid = (smallestHight + biggestHight) / 2;
    if (check(mid) == true){
        ans = mid;
        biggestHight = mid - 1;
    }
    else{
        smallestHight = mid + 1;
    }
}

此过程花费时间复杂度 $O(logn)$.

树的搜索与合法检验

自底而上（从叶至根） 搜索整棵树，并在过程中维护 $i$ 号节点的历经的深度 depth[i]，并完成对应重构，统计达到测试高度值 $h$ 所需重构操作数 cnt，并查验所需操作数是否合法：

• 若向上维护过程中，节点 $i$ 的第 $j$ 个子节点 $v_j$ 累计历经深度达到测试高度值 $h$，则操作数 cnt 自加一，后续操作无需进行；

代表子节点 $v_j$ 已断开与 $i$ 号节点的连接，重新连接至 $1$ 号根节点，后续节点 $v_j$ 不再参与对父节点 $i$ 的历经深度值贡献。

• 否则更新节点 $i$ 的历经深度值，为所有未断开子节点中最大的历经深度值加一；
• 完成搜索后，若所需重构操作数 cnt 不超过题目规定范围 k，则测试高度值 h 可达。

bool check(int h){
    for (int i = 1; i <= n; i ++){
        depth[i] = 1;
    }
    int cnt = 0;
    
    for (int i = n; i >= 2; i --){
        int s = a[i].son.size();
        for (int j = 0; j < s; j ++){
            int v = a[i].son[j];
            if (depth[v] == h){
                cnt ++;
                continue;
            }
            depth[i] = max(depth[v]+1, depth[i]);
        }
    }
    return cnt <= k;
}

由于题目保证 $i$ 节点的父节点编号 $p_i<i$，所以根据节点编号从后往前扫描即可完成树的遍历，无需递归。此过程由于每个节点仅会向父节点贡献至多一次，所以时间复杂度为 $O(n)$.

代码

易错点

不能自顶而下（从根至叶） 维护整棵树，否则所需操作数不是最优，下图给出了一组反例：

/*
    debug: from leaf to root V, from root to leaf X
*/
/*
int cnt;
bool check(int root, int h0, int h){
    bool ok = true;
    if (h0 > h){
        cnt --;
        h0 = 1;
    }
    if (cnt < 0){
        return false;
    }
 
    int s = a[root].son.size();
    for (int i = 0; i < s; i ++){
        int v = a[root].son[i];
        ok &= check(v, h0+1, h);
        if (!ok){
            return ok;
        }
    }
    return ok;
}
*/

AC代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200000 + 10;
struct node {
    vector<int> son;
}   a[maxn];
int n, k;

void init(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++){
        a[i].son.clear();
    }
    for (int i = 2; i <= n; i ++){
        int x;
        cin >> x;
        a[x].son.push_back(i);
    }
}

int depth[maxn];
bool check(int h){
    for (int i = 1; i <= n; i ++){
        depth[i] = 1;
    }
    int cnt = 0;
    
    for (int i = n; i >= 2; i --){
        int s = a[i].son.size();
        for (int j = 0; j < s; j ++){
            int v = a[i].son[j];
            if (depth[v] == h){
                cnt ++;
                continue;
            }
            depth[i] = max(depth[v]+1, depth[i]);
        }
    }
    
    return cnt <= k;
}


int main()
{
    int tt;
    cin >> tt;
    while (tt --){
        init();

        int smallestHight = 1, biggestHight = n-1;
        int mid;
        int ans = n-1;

        while (smallestHight <= biggestHight){
            mid = (smallestHight + biggestHight) / 2;
            // cnt = k;
            // root, h0, h
            // if(check(1, 0, mid)){

            if (check(mid) == true){
                ans = mid;
                biggestHight = mid - 1;
            }
            else{
                smallestHight = mid + 1;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

算法时间复杂度为 $O(nlogn)$.