两种树的直径求法
两遍DFS
优点:方便记录直径的两端点。
缺点:无法除理带负权的树。
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); }
树形DP
优点:短,可以处理有负权的树。
缺点:不好记录端点,容易打错。
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]); } } }