我先整理一下吧，不整理的话搞不好过两天我自己都忘了
树的直径是指一颗树上距离最远的两个点之间的距离。也叫树的最长路
树的直径是指树的最长简单路。
求法: 两遍BFS :先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径；
原理: 设起点为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
