树的直径问题

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

原理: 设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点

证明:

1. 如果u 是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2. 如果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