注释里面写得比较清楚了。谢谢大佬呜呜呜。快疯了。
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=2e5+5;
inline int read(){
char c=getchar();int x=0,f=1;
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=0;
for(;c<='9'&&c>='0';c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?x:-x;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
inline void swap(int &a,int &b){a^=b^=a^=b;}
//============================================================
struct edge{
int u,v,nxt;
}ed[M<<2],en[M<<2];
int head[M],cnt_edge,son[M],he[M],cnt_new,fa[M],dep[M];
int depmax,depsec,poimax,poisec,poi;
bool vis_tot[M],vis[M],fl=0;
inline void add_edge(int u,int v){
ed[++cnt_edge]=(edge){u,v,head[u]};
head[u]=cnt_edge;son[u]++;
}
inline void change(int x,int no){
if(x>=depmax)depsec=depmax,depmax=x,poisec=poimax,poimax=no;//如果比最大的还大,那么最大的就是第二大的了,
else if(x<depmax&&x>depsec)depsec=x,poisec=no;//如果比第二大的大,那么这个节点就是第二大的了
}
inline void dfs_son(int x,int fat){
if(son[x]==1)change(dep[x],x);//是叶子节点才更新,我关注的是节点的编号而不是具体的距离是多少,所以距离是到root的还是end的不重要
for(int i=head[x];i;i=ed[i].nxt){
int v=ed[i].v;
if(v!=fat&&!vis_tot[v])dfs_son(v,x);//不往回走且不往直径走
}
}
inline void dfs_find(int x,int fat){
fa[x]=fat,dep[x]=dep[fat]+1;//记录fa和dep
if(son[x]>=3&&dep[x]>depmax)depmax=dep[x],poi=x;//如果可以作为直径的端点且需要更新才更新
for(int i=head[x];i;i=ed[i].nxt){
int v=ed[i].v;
if(v!=fat)dfs_find(v,x);
}
}
//================================================================
int main(){
int n=read(),root=0;
for(int i=1;i<n;i++){
int u=read(),v=read();
add_edge(u,v),add_edge(v,u);
if(son[u]>=3)root=u;
if(son[v]>=3)root=v;
}
// for(int i=1;i<=cnt_new;i++)printf("%d %d\n",en[i].u,en[i].v);
//我发现没有必要建新图了,因为两个端点的链上可以有两个儿子,如果只将有三个儿子的点加入新图,可能会“断”
//要做的就是遍历找直径的时候只将有三个儿子的点作为终点,这样就可以找到两个端点(其实我们只需要找到两个端点就够了)
dfs_find(root,0);
root=poi;depmax=0;dep[root]=0;
dfs_find(root,0);//
int end=poi;depmax=0;//前面是找以儿子个数大于2个的节点建的新树的直径两个端点,分别是 root和end;
while(poi!=root){
vis_tot[poi]=1;poi=fa[poi];//标记直径上的点,防止遍历子树的时候往上跑了
}
dfs_son(root,0);
int t1=poimax,t2=poisec;//记录这一个子树的最深两个点
depmax=depsec=0;
dfs_son(end,fa[end]);
printf("%d %d\n%d %d",t1,poimax,t2,poisec);
return 0;
}