51nod-2621 樹上距離（tarjian離線求LCA）

​​51nod-2621 樹上距離​​

題目

求樹上兩點最短距離，q次查詢

分析

按有向樹存，選出一個根節點。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 9999991;
const int N = 1e3 + 10;

int n, q, nn, x, y, z, r;
struct node{
    int v, l;                       //存樹時，v 代表指向的節點，l 邊距離
    node(int v, int l):v(v),l(l){}  //存查詢時，v 代表關系節點，l 查詢序号
};
vector<node> tr[N];     //有向樹
vector<node> ask[N];     //查詢
int rt[N], dis[N], fa[N], vis[N], ans[N];

int find(int x){            //并查集
    return fa[x] = fa[x] == x ? x : find(fa[x]);
}

void tarjian(int rt){                   //就是 dfs 序周遊樹
    for(auto x : tr[rt]){
        // d("fds");
        dis[x.v] = dis[rt] + x.l;     //求節點到根節點距離
        tarjian(x.v);
        fa[x.v] = rt;                   //回溯的時候标記
    }
    vis[rt] = 1;
    for(auto x : ask[rt]){
        if(vis[x.v]){                   //如果跟 rt 節點有關系的節點 x 通路過，LCA就是 find(x)
            // d("fds");
            ans[x.l] = dis[x.v] + dis[rt] - 2 * dis[find(x.v)];
        }
    }
}

int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n - 1; i++){
        scanf("%d%d%d", &x, &y, &z);
        tr[x].push_back(node(y, z));
        rt[y]++;
    }
    for(int i = 1; i <= n; i++){    //找跟節點
        fa[i] = i;
        if(!rt[i]){
            r = i;
        }
    }
    for (int i = 0; i < q; i++){
        scanf("%d%d", &x, &y);
        ask[x].push_back(node(y, i));
        ask[y].push_back(node(x, i));
    }
    tarjian(r);
    for(int i = 0; i < q; i++){
        printf("%d\n", ans[i]);
    }
    return 0;
}