SP20775

题面

有一个树，

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

的这两条边）。

代码

CPP

#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;
}

文章操作

题面

题解

代码

相关推荐

评论

SP20775