C++树形结构（2 树的直径）

目录

1.定义：

2.直径的性质：

3.树的直径求解方法：

4.直径端点求解方法：

朴素方法：

优化方法：

5.例题：

6.直径公共点：

7.例题：

8.去掉再加上：

9.例题：

---

1.定义：

树的直径是树上两点间距离的最大值。即树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链

最长链：4-2-1-7-6-3

所以这颗树的直径是15，直径路径为4-2-1-3-6

2.直径的性质：

直径的性质1：直径的端点一定是叶子节点

直径的性质2：任意点的最长链端点一定是直径端点

直径的性质3：如果一棵树有多条直径且边权都为正，那么它们必然相交，且有极长连续段（可以是一个点，交点为树的中心）

直径的性质4：树T1的直径为x,y，树T2的直径为s,t。现有一边u,v与两颗树相连，新树的直径端点一点是x,y,s,t中的两个

3.树的直径求解方法：

引理性质2：任意点的最长链端点一定是直径端点。方法：我们随意找一个点x,进行dfs找到最长链的端点s,再以端点s做第二遍dfs，此时可以找到直径的第二个端点t。此时端点s到t的距离就是树的直径。

输入一颗无根树，第一行为一个正整数n(nx>>y>>z; v[x].push_back(y); v[y].push_back(x); w[x].push_back(z); w[y].push_back(z); } dfs(1,0);//寻找直径 memset(data,0,sizeof data);//清空距离 dfs(pl,0);//从pl出发寻找端点 couty>>z; v[x].push_back(y); v[y].push_back(x); w[x].push_back(z); w[y].push_back(z); } dfs1(1,0); memset(data,0,sizeof data); maxn=0,l=sum; dfs2(l,0); memset(data,0,sizeof data); maxn=0,r=sum; dfs3(r,0); if(l>r) swap(dl,s),swap(l,r);//保证做端点较小 for(int i=1; i