树的直径

树上任意两点最长的距离即为树的直径，树的直径可以有多条。一般有两种方法求树的直径：1.使用两次
DFS,2.树形dp 时间复杂度都是o(n)。

这里只记录双DFS做法：
第一次任意选一个点进行DFS/BFS，找到离它最远的点，此点就是最长路的一个端点，再以此点进行DFS/BFS ，找到离它最远的点，此点就是最长路的另一个端点，于是就找到了树的直径。

洛谷B4016

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[++ idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx;
}
int d[N];
void dfs(int f, int u, int len)
{
    d[u] = len;
    for (int i = h[u]; i; i = ne[i])
    {
        int j = e[i];
        if (j != f) dfs(u, j, len + w[i]);
    }
}
int find_max_idx(int arr[], int n) {
    int idx = 0;
    for (int i = 1; i <= n; i++) if (d[idx] < d[i]) idx = i;
    return idx;
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n-1; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        add(a, b, 1);
        add(b, a, 1);
    }
    dfs(-1, 1, 0);
    int idx = find_max_idx(d, n);

    dfs(-1, idx, 0);
    idx = find_max_idx(d, n);
    printf("%d\n", d[idx]);
    return 0;
}