代码不知道上了多少补丁。。终于过了
用类似拓扑排序的办法收缩整棵树得到x，然后找到x直连的最远的和最近的点
只有这三个点可能是根，依次判一下即可
另外题解的第一种方法时找直径，然后判两端点+重心+所有直连重心的叶子节点，感觉这样子复杂度爆炸啊。。（如果是遍历所有叶子节点的话）
#include<bits/stdc++.h> using namespace std; #define maxn 200005 struct Edge{int to,nxt;}e[maxn<<1]; int head[maxn],tot; void init(){ memset(head,-1,sizeof head); tot=0; } void add(int u,int v){ e[tot].to=v;e[tot].nxt=head[u];head[u]=tot++; } int d[maxn],n,degree[maxn]; void dfs1(int u,int pre,int deep){ if(degree[u]>2)return; if(degree[u]==1){ d[u]=deep;return; } for(int i=head[u];i!=-1;i=e[i].nxt){ int v=e[i].to; if(v==pre)continue; dfs1(v,u,deep+1); } } int dis[maxn]; int judge(int u){ queue<int>q; memset(dis,0,sizeof dis); q.push(u);dis[u]=1; int tmp1=1,tmp2=degree[u]; while(q.size()){ int x=q.front();q.pop(); if(dis[x]!=tmp1){ tmp1=dis[x]; tmp2=degree[x]; } else if(tmp2!=degree[x])return 0; for(int i=head[x];i!=-1;i=e[i].nxt){ int y=e[i].to; if(dis[y])continue; dis[y]=dis[x]+1; q.push(y); } } return 1; } int main(){ init(); cin>>n; if(n==1){ puts("1"); return 0; } for(int i=1;i<n;i++) { int u,v; cin>>u>>v; add(u,v);add(v,u); degree[u]++,degree[v]++; } queue<int>q; int cnt=0,rt,tmp[maxn]; memcpy(tmp,degree,sizeof degree); for(int i=1;i<=n;i++) if(degree[i]==1) q.push(i),cnt++; while(cnt!=n){ int x=q.front();q.pop(); for(int i=head[x];i!=-1;i=e[i].nxt){ int y=e[i].to; if(tmp[y]==1)continue; else if(--tmp[y]==1){ q.push(y); cnt++; if(cnt==n)rt=y; } } } if(judge(rt)){cout<<rt;return 0;} memset(d,0,sizeof d); for(int i=head[rt];i!=-1;i=e[i].nxt){ int v=e[i].to; dfs1(v,rt,1); } int Max=0,Min=1000000,s=-1; for(int i=1;i<=n;i++) if(d[i] && Max<d[i]){ Max=d[i];s=i; } if(s!=-1){ if(judge(s)){cout<<s;return 0;} } s=-1; for(int i=1;i<=n;i++) if(d[i] && Min>d[i]){ Min=d[i],s=i; } if(s!=-1){ if(judge(s)){cout<<s;return 0;} } cout<<-1; }
转载于:https://www.cnblogs.com/zsben991126/p/11009260.html
