Luogu P3174 题解：树上路径DP

题意

给定一棵树，对于树上任意路径$P$，定义毛毛虫为点集
$$
\{v : \exists u \in P, \text{dist}(u, v) \le 1 \}
$$
中元素个数，求树上所有路径的毛毛虫的最大值。

解析

本题涉及树上路径。拿到题首先通过样例理解题意，并思考如何构造状态量。

不难发现无法直接将“子树中所有路径的毛毛虫的最大值”转化到父亲的对应值。例如对于以5为根的子树，其所有路径的毛毛虫的最大值是8，对应的路径是9（或10或11或7）到12（或13或8）的那条；但是从5转移到其父亲1时，毛毛虫最大的路径的一端显然不再在以8为根的子树中。这启示我们为了使得转移得以进行，我们需要一个方便“子树拼接”的状态定义，故不妨作如下定义：
$$
f(u):= 在u的子树中，以u为其中一个端点的路径的毛毛虫最大值
$$
注意此时我们并未考虑$u$的父亲，因为我们试图将$u$的子树和树的其他部分分离后处理问题。使用这一定义，状态转移是容易的：先算出$u$的儿子$v$中$f(v)$的最大值，再加上$u$自身和$u$其他的儿子：
$$
f(u) = \max_{v \in \text{son}(u)}\{f(v)\} +1 + (|\text{son}(u)|-1)
$$
边界情况是对于叶子节点，
$$
f(u)=1
$$
下面我们再考虑用$f(u)$去求更一般的$g(u)$：
$$
g(u):=在u的子树中，经过u的所有路径的毛毛虫的最大值
$$
$g(u)$也是容易求的。因为路径需要经过$u$，所以想象成路径两端还可以向下延伸，也就是两条以$u$的儿子为一个端点的毛毛虫最大路径。不过这个想象是有欠缺的，因为可能$u$只有一个儿子，但这也是容易处理的情况。简单地说，当$u$有至少两个儿子的时候，
$$
g(u) = \max_{v_1, v_2 \in \text{son}(u), v_1 \not=v_2}\{f(v_1) +f(v_2)\} + 1 + (|\text{son}(u)|-2)
$$
我们观察到$g(u)$距最后的答案只有一步之遥。任意一条路径都存在于某个最小的子树中，即以这个路径中深度最浅的那个点为根的子树上。因此我们枚举这个路径中深度最浅的那个点$u$，对$g(u)$取最大值；但还需注意我们此前一直将$u$的父亲不予考虑，现在则需要加回来（除非$u$是根节点），才是最终答案。

在编码过程中需要注意，当我们用无向图的方式存树的时候，因为每条边被存储了两次，所以son[u].size()表示的是u的度而不是u的儿子个数；需要将u的度减去u的父亲（根节点除外）才能得到u的儿子个数。另外，本题中将所有最大值的初始值都设为1为好，可以兼顾各种边界情况（如叶子节点，或整棵树只有一个节点）。

代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(register int i=(int)(from);i<=(int)(to);++i)
#define For(i,to) for(register int i=0;i<(int)(to);++i)
typedef long long ll;
inline ll read(){
    ll x=0; ll sign=1; char c=getchar();
    while(c>'9' || c<'0') {if (c=='-') sign=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*sign;
}

int n, m;
#define N 301000
vector<int> son[N]; int fa[N];
int g[N], f[N];

int sonsize(int u) {
    return son[u].size() - !!fa[u];
}

void dfs(int u) {
    int mx1 = 1, mx2 = 1;
    for(int v : son[u]) if (v != fa[u]) {
        fa[v] = u;
        dfs(v);

        if (f[v] >= mx1) {
            mx2 = mx1, mx1 = f[v];
        } else if (f[v] >= mx2) {
            mx2 = f[v];
        }
    }
    f[u] = mx1 + sonsize(u);
    g[u] = mx1 + mx2 + sonsize(u) - 1;
}


int main() {
#ifdef D
    freopen("3174.in", "r", stdin);
    double TIMEA = clock();
#endif
    n = read(), m = read();
    For(_, m) {
        int a = read(), b = read();
        son[a].push_back(b);
        son[b].push_back(a);
    }

    dfs(1);

    int ans = 1;
    rep(i, 1, n) {
        ans = max(ans, g[i] + !!fa[i]);
    }

    cout << ans << endl;

#ifdef D
    double TIMEB=clock();
    printf("\n# Time consumed: %.3fs.\n", (TIMEB-TIMEA)/1000);
#endif
    return 0;
}