题目描述

求出树的直径上的点的编号 直径存在多条 所以需要全部求出来

样例

dfs几次即可 $O(n)$

和y总不同的写法 求出树的2个端点
直径的性质：与一点距离最远的2个点一定是直径的一个端点
我们求出2个端点 分别再判断是否能有另一个点与他的距离加起来==直径

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5+10;
struct Edge{
    int v,next;
}edge[N<<1];
int head[N],tot;
void add(int u,int v){
    edge[++tot]={v,head[u]};
    head[u]=tot;
}
int tree_len=0,dis[N],x,y,n;
void dfs(int u,int fa){
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v ;
        if(v!=fa){
            dis[v]=dis[u]+1;
            dfs(v,u);
        }
    }
}
void get_len(){
    dfs(0,0);
    x=y=0;
    for(int i=0;i<n;i++){
        if(dis[x]<dis[i])x=i;
    }
    memset(dis,0,sizeof dis);
    dfs(x,x);
    for(int i=0;i<n;i++){
        if(dis[y]<dis[i])y=i;
    }
    tree_len=dis[y];
}
int dis1[N],ans[N];
void dfs1(int u,int fa){
    dis1[u]=0;
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].v;
        if(v!=fa){
            dfs1(v,u);
            dis1[u]=max(dis1[v]+1,dis1[u]);
        }
    }
    if(dis1[u]+dis[u]==tree_len)ans[u]=1;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    get_len();
    dfs1(x,x);
    memset(dis,0,sizeof dis);
    memset(dis1,0,sizeof dis1);
    dfs(y,y);
    dfs1(y,y);
    for(int i=0;i<n;i++)
    if(ans[i])printf("%d\n",i);
    return 0;
}