CF-1739D 題解

CF 1739D.

本來這是想到才要寫的，但是一不小心把暫時新增的檔案部屬上來，為了不要讓這個空白文章出現太久，就先寫一下吧

題敘：

有一棵樹，可以對它做 $k$ 次以下操作：

• 選擇一個點對 $u, v$（$u$ 是 $v$ 的父親），斷開這條邊，並將 $v$ 及其子樹連到 $1$

求 $k$ 次操作後這棵樹的高度最少是多少

解法:

可以發現這個性質：目標高度越大，所需操作次數越少

根據這點可以得出這題可以使用對答案二分搜的技巧，至於該怎麼實作 check 函數呢？

對一棵樹，要經過數次操作使得高度變成 $h$ 的方法有兩種：

1. 從樹根往下走，當深度超過 $h$ 就做一次操作
2. 從樹葉往上走，當深度超過 $h$ 就做一次操作

畫出任意一棵樹的話會發現：第一種方法的操作點深度會比第二種方法要深，而這會產生什麼影響呢？

對於一棵樹，深度越深，點的數量就會越多，因此我們的操作點要是盡可能的淺，就能夠減少操作次數，所以我們在實作檢查的 dfs 時，可以利用第二種方式來實作，大概就是長這樣：

int n, m;
int dep[MAXN], p[MAXN];
vector<int> G[MAXN];
 
int cnt;
 
void dfs(int i, int mid) {
    for (int j: G[i]) {
        dfs(j, mid);
        cmax(dep[i], dep[j]);
    }
 
    dep[i] += (i != 1);
 
    if (dep[i] == mid && p[i] != 1) {
        cnt++;
        dep[i] = 0;
    }
}

完整程式碼

#define MAXN 200005
#define MAXM 1000005 
int n, m;
int dep[MAXN], p[MAXN];
vector<int> G[MAXN];
 
int cnt;
 
void dfs(int i, int mid) {
    for (int j: G[i]) {
        dfs(j, mid);
        cmax(dep[i], dep[j]);
    }
 
    dep[i] += (i != 1);
 
    if (dep[i] == mid && p[i] != 1) {
        cnt++;
        dep[i] = 0;
    }
}
 
bool check(int mid) {
    mx = cnt = 0;
    for (int i = 1; i <= n; i++) {
        dep[i] = 0;
    }
    dfs(1, mid);
 
    return !(cnt > m);
}
 
void sol() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        G[i].clear();
        dep[i] = 0;
    }
    p[1] = 1;
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
        G[p[i]].pb(i);
    }
 
    check(1);
 
    int l = 1, r = n - 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid)) 
            r = mid;
        else
            l = mid + 1;
    }
    cout << r << endl;
}