两遍DFS
优点：方便记录直径的两端点。
缺点：无法除理带负权的树。
树形DP
优点：短，可以处理有负权的树。
缺点：不好记录端点，容易打错。
最初每条路要走两遍，修一条路就可使与它形成环的路少走一遍，先找到直径，然后把与直径形成环的点边的边权改为-1（因为每条路至少走一遍，第一次少走1，第二次就不能少走了），然后再找一次直径。
#includeusing namespace std; const int MM=1000006,inf=0x3f3f3f3f; int dis[MM],nxt[MM*2],to[MM*2],head[MM],q[MM*2],dep[MM],f[MM],tot,maxl,s,t,n,k,u,v,zj[MM],lzj1,lzj2; void add(int u,int v) { nxt[++tot]=head[u]; head[u]=tot; to[tot]=v; q[tot]=1; } void dfs(int now,int deep,int fa) { dep[now]=deep; f[now]=fa; for(int i=head[now];i;i=nxt[i]) if(to[i]!=f[now])dfs(to[i],deep+1,now); } void dfs1(int now,int len) { if(len>maxl) { maxl=len; s=now; } for(int i=head[now];i;i=nxt[i]) if(to[i]!=f[now])dfs1(to[i],len+1); } void dfs2(int now,int len,int fa) { if(len>maxl) { maxl=len; t=now; } for(int i=head[now];i;i=nxt[i]) if(to[i]!=fa)dfs2(to[i],len+1,now); } void dfs3(int now) { for(int i=head[now];i;i=nxt[i]) { if(to[i]!=f[now]) { dfs3(to[i]); lzj2=max(lzj2,dis[now]+dis[to[i]]+q[i]); dis[now]=max(dis[now],dis[to[i]]+q[i]); } } } int main() { cin>>n>>k; for(int i=1;i1;i++) { cin>>u>>v; add(u,v); add(v,u); } dfs(1,1,0); dfs1(1,0); dfs2(s,0,0); if(dep[s]<dep[t]) swap(s,t); while(dep[s]>dep[t]) zj[s]=1,s=f[s]; lzj1=maxl; if(k==1) { cout<1)*2-lzj1+1; return 0; } while(s!=t) { zj[s]=1,zj[t]=1; s=f[s],t=f[t]; } zj[s]=1; for(int i=1;i) { if(zj[i]) { for(int j=head[i];j;j=nxt[j]) { if(zj[to[j]]) q[j]=-1; } } } dfs3(1); //cout< cout<1 )*2-(lzj1+lzj2)+2; return 0; }
Original: https://www.cnblogs.com/29taorz/p/15342614.html
Author: T_X蒻
Title: 两种树的直径求法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/644239/
转载文章受原作者版权保护。转载请注明原作者出处！