我先整理一下吧气堕，不整理的話搞不好過兩天我自己都忘了
樹的直徑是指一顆樹上距離最遠的兩個點之間的距離。也叫樹的最長路
樹的直徑是指樹的最長簡單路。
求法: 兩遍BFS :先任選一個起點BFS找到最長路的終點，再從終點進行BFS，則第二次BFS找到的最長路即為樹的直徑触徐；
原理: 設(shè)起點為u,第一次BFS找到的終點v一定是樹的直徑的一個端點
證明:
- 如果u 是直徑上的點，則v顯然是直徑的終點(因為如果v不是的話狐赡，則必定存在另一個點w使得u到w的距離更長撞鹉，則于BFS找到了v矛盾)
- 如果u不是直徑上的點，則u到v必然于樹的直徑相交(反證),那么交點到v 必然就是直徑的后半段了
所以v一定是直徑的一個端點，所以從v進行BFS得到的一定是直徑長度
bfs寫法
LL d[2][maxn];
queue<int > Q;
int bfs(int u,int idx) //樹的直徑
{
memset(d[idx],-1,sizeof(d[idx]));
while(!Q.empty()) Q.pop();
d[idx][u] = 0;
Q.push(u);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i = hd2[u];~i;i = e[i].next)
{
if(d[idx][e[i].v]==-1)
{
d[idx][e[i].v] = d[idx][u] + e[i].w;
Q.push(e[i].v);
}
}
}
LL ret = -1;
int id = 0;
for(int i=1;i<=cnt;i++)
if(ret < d[idx][i]) ret = d[idx][id = i];
return id;
}
dfs寫法
void TreeDia(int u,int pre,int len)
{
if(len > max_len) st = u,max_len = len;
for(int i=0;i<g[u].size();i++)
{
int v = g[u][i].v;
if(v==pre) continue;
TreeDia(v,u,len+g[u][i].w);
}
}
還是dfs好寫o((>ω< ))o
