树的直径

1. 定义:
   (1)树中最远两个节点之间的距离被称为树的直径;
   (2)或是连接这两点的路径
   直径既是一个数值概念，也可代指一条路径
2. 求解:
   (1)树形DP:
   1)要维护的数组：
   D[x]:节点x出发走向以x为根的子树，能够到达的最远节点的距离
   F[x]:经过节点x的最长链的长度(x作为根 暂时这么理解)
   2)数组的维护:

            D[x] = max(d[yi] + edge(x, yi)) //yi为x的子节点
            F[x] = max(d[yi] + edge(x, yi) + edge(x, yj) + d[yj]) //yi与yj分别为x不同的子节点

    3)计算过程分析:
        分析D[x]的计算过程：
            枚举x的子节点，设x其中两个子节点为i j(i>j),当枚举到i时，D[x]存放的为x序号小于i的子节点能到达的最远距离
            即,D[x] = max(d[yj] + edge(x, yj)) (1 <= j < i)
        分析F[x]的计算过程:
            ①枚举x的子节点，设第一层循环枚举到x的子节点为i(遍历以x为根的路径经过的第一个节点),第二层循环枚举到子节点j(j < i)(遍历以x为根的路径经过的第二个节点),则此时的F[x] = max(D[yk1] + edge(x, yk1) + edge(x, yk2) + D[yk2]) ,其中1 <= k1 <= i, 1 <= k2 <= j < i
            ②上式可以转化为: F[x] = max(D[yk1] + edge(x, yk1)) + max(D[yk2] + edge(x, yk2)), 其中1 <= k1 <= i, 1 <= k2 <= j < i
            ③结合D[x]的搜索过程,F[x] = max(D[x] + D[yk1] + edge(x, yk1)) ,其中 1 <= k1 <= i
        综上分析：使用一层循环遍历x的子节点i, 先用D[x] + D[yi] + edge(x, yi) 更新 F[x]; 后使用D[yi] + edge(x, yi)更新D[x]
    4)

void dp(int x){
    st[x] = 1;
    for(int i = h[x]; ~i; i = ne[i]){
        int j = e[i];
        if(st[j]) continue;
        dp(j); // 递归i的子节点
        ans = max(ans, d[x] + d[j] + w[i]); // 此时的d[x]使用下标小于i的子节点更新
        d[x] = max(d[x], d[y] + w[i]);
    }
}

(2) _两次BFS求树的直径_:
    1) 思路: 从任一节点出发，使用BFS或DFS找到距离起始节点的最远点p; 再从节点p出发使用BFS或DFS找到距离p的最远点q, p->q的路径即为树的一条直径
    2)

        int ans; //最远节点编号
        void dfs(int u, int fa){ 
            for(int i = h[u]; ~i; i = ne[i]){
                int j = e[i];
                if(j == fa) continue;
                d[j] = d[u] + 1;
                if(d[j] > d[ans]) ans = j;
                dfs(j, u);
            }
        }

        int main()
        {
            // ...
            dfs(1, 0);
            int p = ans;
            d[p] = 0;
            dfs(p, 0);
            int q = ans;
            //p q 为直径的两端点,d[q]为直径的长度
            // ...
        }