SP20775

DDF_ · 2025-10-27 21:46:32 · 题解

题面

有一个树，q 次询问，每次求以 x 为根的子树中的最长路径长度！（话说这题为什么没人写啊

题解

树形 dp。

定义 f_{x} 是以 x 为根的子树中的最长路径长度（就是题目中要求的）。

对 f_{x} 进行分讨：

• 这条路径不经过 x，那就是在其子节点的子树上取最长路径。
• 这条路径经过 x，那就是在子树中取两条路径，这两条路径都以 x 的子节点为路径端点，然后把这两条路径通过 x 串起来。

令 y 是 x 的子节点。

第一种情况：f_{x}=\max(f_{y})。

第二种情况比较难处理，但发现以 x 为路径端点的最长路径也可以树形 dp 求出来，设这个值为 g_{x}，那么 g_{x}=\max(g_{y})+1。

则对于第二种情况，取子节点中 g_{y} 的最大值和次大值，加起来再加上 2 即可（就是加上连到 x 的这两条边）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,r,q;
int head[N],to[2*N],nxt[2*N],idx;
int f[N][5];
void add(int x,int y) {
    nxt[++idx]=head[x],head[x]=idx,to[idx]=y;
    return;
}
void dfs(int x,int fa) {
    int mx=0;
    for(int i=head[x];i;i=nxt[i]) {
        int y=to[i];
        if(y!=fa) {
            dfs(y,x);
            f[x][0]=max(f[x][0],f[y][0]);
            if(f[y][1]+1>f[x][1]) {
                mx=f[x][1];
                f[x][1]=f[y][1]+1;
            }
            else if(f[y][1]+1>mx) mx=f[y][1]+1;

        }
    }
    f[x][0]=max(f[x][0],mx+f[x][1]);
}
int main() {
    scanf("%d",&n);
    for(int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),add(x,y),add(y,x);
    scanf("%d",&r);
    dfs(r,0);
    scanf("%d",&q);
    while(q--) {
        int x;
        scanf("%d",&x);
        printf("%d\n",f[x][0]);
    }
    return 0;
}