树的直径

直径被定义为 一棵树上最长的简单路径

求直径长度

随机选一个点跑最短路，找到距离最大的任意一个点$d_1$再跑一次最短路，找出距离最大的那个点$d_2$

$d_1\to d_2$ 就是这棵树的直径

简单来说 就是两次dijk

参考代码：

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    vector<int> dist(n + 1, 1e18);
    dist[1] = 0;
    pq.emplace(0, 1);
    while (pq.size())
    {
        auto [w, u] = pq.top();
        pq.pop();
        if (w > dist[u])
        {
            continue;
        }
        for (auto [nxt, nxtw] : adj[u])
        {
            if (nxtw + w < dist[nxt])
            {
                dist[nxt] = w + nxtw;
                pq.emplace(dist[nxt], nxt);
            }
        }
    }
 
    int maxdist = -1;
    int d1;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] != 1e18)
        {
            if (dist[i] > maxdist)
            {
                maxdist = dist[i];
                d1 = i;
            }
        }
    }
 
    fill(all(dist), 1e18);
    dist[d1] = 0;
    pq.emplace(0, d1);
    while (pq.size())
    {
        auto [w, u] = pq.top();
        pq.pop();
        if (w > dist[u])
        {
            continue;
        }
        for (auto [nxt, nxtw] : adj[u])
        {
            if (nxtw + w < dist[nxt])
            {
                dist[nxt] = w + nxtw;
                pq.emplace(dist[nxt], nxt);
            }
        }
    }
 
    maxdist = -1;
    int d2;
    for (int i = 1; i <= n; i++)
    {
        if (dist[i] != 1e18)
        {
            if (dist[i] > maxdist)
            {
                maxdist = dist[i];
                d2 = i;
            }
        }
    }
 

求直径路径

在直径两个端点已经确定情况下 可以对 $d_1$ 用一次 $dijk$ 求得每一个节点在$d_1$方向上的父节点 ，把所有的节点都存入$parent$ 数组中，然后从d2开始遍历该数组即可获得路径

$d_1$ 的这次 $dijk$ 可以跟上面合并 降低常数

    vector<int> parent(n + 1, 0);
    function<void(int, int)> get_path_dfs = [&](int u, int p)
    {
        parent[u] = p;
        for (auto &[nxt, _] : adj[u])
        {
            if (nxt != p)
            {
                get_path_dfs(nxt, u);
            }
        }
    };
    get_path_dfs(d1, 0);
 
    vector<int> zhijing; // 直径
    for (int cur = d2; cur != 0; cur = parent[cur])
    {
        zhijing.push_back(cur);
    }
    reverse(all(zhijing));