题目描述
W 市的交通规划出现了重大问题,市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。
但由于人员不足,W 市市长决定只在最需要安排人员的路口安排人员。
具体来说,W 市的交通网络十分简单,由 n 个交叉路口和 n−1 条街道构成,交叉路口路口编号依次为 0,1,…,n−1 。
任意一条街道连接两个交叉路口,且任意两个交叉路口间都存在一条路径互相连接。
经过长期调查,结果显示,如果一个交叉路口位于 W 市交通网最长路径上,那么这个路口必定拥挤不堪。
所谓最长路径,定义为某条路径 p=(v1,v2,…,vk),路径经过的路口各不相同,且城市中不存在长度大于 k 的路径(因此最长路径可能不唯一)。
因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。
样例
输入样例:
10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9
输出样例:
0
1
2
3
4
5
6
8
9
C++ 代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=200010,M=2*N;
int e[M],ne[M],head[M],d1[N],d2[N],up[N],p[N]; //p[a]表示结点a向下的最长路径经过的子结点
int id;
int n,maxz;
void add(int a,int b){
e[id]=b;
ne[id]=head[a];
head[a]=id++;
}
void bfs1(int u,int fa){ //从下往上遍历
for(int i=head[u];i!=-1;i=ne[i]){
int j=e[i];
if(j!=fa){
bfs1(j,u);
int distance=d1[j]+1; //更新向下的最长长度
if(distance>d1[u]){
d2[u]=d1[u];
d1[u]=distance;
p[u]=j;
}
else if(distance>d2[u]){
d2[u]=distance;
}
}
}
maxz=max(maxz,d1[u]+d2[u]);
}
void bfs2(int u,int fa){ //从上向下遍历
for(int i=head[u];i!=-1;i=ne[i]){
int j=e[i];
if(j!=fa){
up[j]=up[u]+1;
if(p[u]!=j){
up[j]=max(up[j],d1[u]+1);
}
else{
up[j]=max(up[j],d2[u]+1); //u向下的最长路径经过子结点j,不选最长路径,选次长路径
}
bfs2(j,u);
}
}
}
int main(){
cin>>n;
memset(head,-1,sizeof head);
for(int i=1;i<=n-1;i++){
int a,b;
scanf("%d %d",&a,&b);
add(a,b);
add(b,a);
}
bfs1(0,-1);
bfs2(0,-1);
for(int i=0;i<n;i++){
int m1=max(d1[i]+up[i],d1[i]+d2[i]);
if(m1==maxz){
printf("%d\n",i);
}
}
}
题目分析
题目的本质是求树的直径和经过直径的所有的结点(直径可能不唯一,所以求所有的直径经过的点)
思路:树的直径的相关问题
1.从树中任选一个结点a,找出距离a最长的点b,从b出发找距离b最长的点k,bk的长度等于树的直径的长度
2.树形dp:求树中所有结点向下的最长长度和次长的长度的和,求最大值maxz,maxz为树的直径的长度
求所有经过直径的结点:遍历树的结点,一个结点有三个值:up[a]表示a向上的最大长度,d1[a]表示a向下的最大长度,d2[a]表示a向下的次大长度,选择三个值的最大两个值相加,若相加的和等于直径,则结点位于直径上