题解：P10794 『SpOI - R1』架子鼓可以站 C

· · 题解

题目大意

可以任意进行多次操作，每次可以选择一个叶子节点 v，将 v 到根的简单路径中的一条边删掉，再在 v 与根之间连一条边，问最终树的直径最长为多少。

分析

一开始本人考虑每个子树内的最长链，最后找到根节点的两个最大子树求和，但是两条链可能在同一个子树内，这也是这道题的难点。

我们分步考虑：

  1. 不做操作：答案是树的直径。
  2. 只进行 1 次操作：选一条从叶子出发的、不经过根节点的路径，删除路径上深度最小的点的父亲边，然后将其挂在根节点的下方。再选另一条从根节点出发的路径拼成答案（注意：两条路径不能相交，否则找不到合法的可以删除的边）。
  3. 进行 2 次操作：等价于选择了两条不交的、且不经过根节点的路径分别挂在根节点下方，答案为选择的两条路径长度之和加上 2。
  4. 进行 3 次及以上的操作是没有意义的，因为不可能存在一条路径同时覆盖了三条新增的边。
  5. 不做操作和只做一次操作的情况下，也可以认为是选择了两条不交且不经过根节点的路径。可以统一用树形 DP 来做。

目标

在以 u 为根的子树内，划分出两条没有交点的长链。

状态

d[u] 表示 u 子树中端点为 u 的最大链长。

f[u] 表示 u 子树中端点任意的最大链长。

g[u] 表示 u 子树中 2 条链的最大链长和，其中 1 条链端点为 u。

h[u] 表示 u 子树中 2 条链的最大链长和，并且 2 条链端点任意。

D[u][3] 表示端点为儿子 v 的最大、次大、三大链长。

S[u][3] 表示对应的三个儿子的编号。

状态转移

  2. 1. 从 $v$ 子树继承：`f[u]=max(f[u],f[v])`。 2. 经过 $u$ 点：`f[u]=max(f[u],D[u][0]+D[u][1]+2)`。

  1. 1. 从 $v$ 子树继承：`g[u]=max(g[u],g[v]+1)`。 2. 以 $u$ 为端点不过 $v$ 的最长链与 $v$ 中的任意最长链拼凑：`g[u]=max(g[u],f[v]+(s[u][0]==v?D[u][1]:D[u][0])+1)`。

  1. 1. 从 $v$ 子树继承：`h[u]=max(h[u],h[v])`。 2. $2$ 条链来自不同子树：`h[u]=max(h[u],f1+f2)`。 3. $1$ 条来自 $v$，$1$ 条过 $u$：`h[u]=max(h[u],f[v]+res+2)`。 4. $1$ 条来自 $v$，$1$ 条过 $u,v$：`h[u]=max(h[u],g[v]+(S[u][0]==v?D[u][1]:D[u][0])+2)`。

  1. 由于链不能经过根节点 1，需要对根的每个子树分别讨论并计算答案，注意加上新建的两条边的贡献：
    1. 子树之内的 2 条链长和，用 h[i] 计算。
    2. 子树之间的 2 条链长和，用 f[i] 拼凑。

这道题也就迎刃而解了。

AC Code：

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define PII pair<int, int>
#define PLL pair<ll, ll>

const ll inf = 2e9, N = 200050, M = 2050, MOD = 1e9 + 7;

ll t, n, u, ans, mx1, mx2; 
ll d[N], f[N], g[N], h[N];
ll D[N][3], S[N][3];
vector<ll> e[N]; 

// 更新最大，次大，三大儿子 分类讨论 
void upd(ll x, ll y, ll dep){
    if(dep > D[x][0]){
        D[x][2] = D[x][1], S[x][2] = S[x][1];
        D[x][1] = D[x][0], S[x][1] = S[x][0];
        D[x][0] = dep, S[x][0] = y;
    }
    else if(dep > D[x][1]){
        D[x][2] = D[x][1], S[x][2] = S[x][1];
        D[x][1] = dep, S[x][1] = y;
    }
    else if(dep > D[x][2]) D[x][2] = dep, S[x][2] = y;
}

// 树形DP 
void dfs(ll now){
    ll f1 = 0, f2 = 0;
    for(ll i : e[now]){
        dfs(i);
        // 从v子树继承 
        d[now] = max(d[now], d[i] + 1);
        upd(now, i, d[i]);
        f[now] = max(f[now], f[i]);
        g[now] = max(g[now], g[i] + 1);
        h[now] = max(h[now], h[i]);
        // 保存两个最佳子树，便于更新h 
        if(f[i] > f1) f2 = f1, f1 = f[i];
        else if(f[i] > f2) f2 = f[i];
    }
    // 从两个最佳子树更新 
    f[now] = max(f[now], D[now][0] + D[now][1] + 2);
    h[now] = max(h[now], f1 + f2);
    // 子树遍历完后再更新 
    for(int i : e[now]){
        g[now] = max(g[now], f[i] + (S[now][0] == i ? D[now][1] : D[now][0]) + 1);
        ll res = 0, cnt = 0;
        if(S[now][0] != i) res += D[now][0], cnt ++;
        if(S[now][1] != i) res += D[now][1], cnt ++;
        if(cnt < 2 && S[now][2] != i) res += D[now][2];
        h[now] = max(h[now], f[i] + res + 2);
        h[now] = max(h[now], g[i] + (S[now][0] == i ? D[now][1] : D[now][0]) + 2);
    }
}

int main(){
    scanf("%lld", &t);
    while(t --){
        scanf("%lld", &n);
        // 记得全部清空！！！ 
        for(int i = 1; i <= n; i ++){
            e[i].clear();
            S[i][0] = S[i][1] = S[i][2] = f[i] = d[i] = h[i] = 0;
            D[i][0] = D[i][1] = D[i][2] = g[i] = -1;
        }
        for(int i = 2; i <= n; i ++){
            scanf("%lld", &u);
            e[u].push_back(i);
        }
        dfs(1);
        // 统计最大链，次大链之和与子树中的两大链的最大值作为答案 
        ans = 0; mx1 = -inf, mx2 = -inf;
        for(int i : e[1]){
            ans = max(ans, h[i] + 2);
            if(f[i] > mx1) mx2 = mx1, mx1 = f[i];
            else if(f[i] > mx2) mx2 = f[i];
        }
        if(n == 2) puts("1"); // 特判 
        else printf("%lld\n", max(ans, mx1 + mx2 + 2));
    }
    return 0;
}