CF2230F

NLFancy · 2026-06-09 16:32:47 · 题解

vp 的时候感觉过的很快？但是大家都不会？

首先是策略问题，先不管爱丽丝选择从哪里开始这次博弈。

当开始博弈之后，每次鲍勃封掉的节点如果满足这个节点的祖先还没有被封或者这个节点本身是不可能被经过的了，显然选择这个点是更劣的。

那么鲍勃能选择就只剩下爱丽丝所在节点的儿子节点了。

每次封掉某个儿子，爱丽丝就会选择一个儿子走过去，进行重复的操作。那么这实际上就是一个子问题，考虑 dp 。

设 dp_u 表示爱丽丝现在在 u 这个节点上，他和鲍勃进行一番博弈后他能得到的最大值。

而每次鲍勃选择点的时候一定会让余下的点的 dp 值最大值最小，那么他一定选择最大值的点封，转移的就是次大值。

上述操作可以通过换根得到最佳的起始点，也就是说我们可以在某个版本的树上 O(n) 的得到答案。

接下来就是对所有的求答案，不难发现每次加入一个点肯定不会使得答案变少，也就是说答案是单调的。

同时，每次如果鲍勃每次封掉子树大小最大的子树的话，答案肯定比上述的最优策略的答案大，那么最优策略的答案也就是 O(\log n) 量级的了。

每次二分当前答案最晚会在什么位置出现，时间复杂度 O(n\log^2n) 可以通过。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, dp[N], dp1[N], tim, tmx, ans[N];
vector<int> G[N];
void dfs(int u, int fa) {
    if(u > tim) return;
    int mx = 0, smx = 0;
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs(v, u);
        if(dp[v] > mx) smx = mx, mx = dp[v];
        else if(dp[v] > smx) smx = dp[v];
    }
    dp[u] = smx + 1;
}
void dfs1(int u, int fa, int xx) {
    if(u > tim) return;
    int mx = xx, smx = 0, ssmx = 0;
    for(int v : G[u]) {
        if(v == fa) continue;
        if(dp[v] > mx) ssmx = smx, smx = mx, mx = dp[v];
        else if(dp[v] > smx) ssmx = smx, smx = dp[v];
        else if(dp[v] > ssmx) ssmx = dp[v];
    }
    dp1[u] = 1 + smx, tmx = max(tmx, dp1[u]);
    for(int v : G[u]) {
        if(v == fa) continue;
        if(dp[v] == mx || dp[v] == smx) dfs1(v, u, 1 + ssmx);
        else dfs1(v, u, 1 + smx);
    }
}
int gt(int x) {
    for(int i = 1; i <= n + 1; i++) dp[i] = dp1[i] = 0;
    tim = x, tmx = 0;
    dfs(1, 0);
    dfs1(1, 0, 0);
    return tmx;
}
signed main() {
    cin >> n;
    for(int i = 1, fa; i <= n; i++) {
        cin >> fa;
        G[fa].push_back(i + 1);
    }
    int mxx = gt(n + 1), nw = 1;
    for(int i = 1; i <= mxx; i++) {
        int l = nw + 1, r = n + 1, as = nw;
        while(l <= r) {
            int mid = l + r >> 1;
            if(gt(mid) == i) as = mid, l = mid + 1;
            else r = mid - 1;
        }
        for(int j = nw + 1; j <= as; j++) ans[j] = i;
        nw = as;
    }
    for(int i = 1; i <= n; i++) cout << ans[i + 1] << " ";
    return 0;
}