HDU-2586 How far away ？（Tarjian_LCA)

​​HDU-2586 How far away ？​​

题目

分析

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define d(x) cout << (x) << endl
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#pragma GCC diagnostic error "-std=c++11"
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4e4 + 10;
const int M = 2e2 + 10;

int t, n, m;
int cnt, num;
struct edge{
    int next, to, w;
} e[N];
int head[N];

struct node{
    int next, to;
    int index;  //查询序号
} ask[N];
int h[N];

int fa[N];      //并查集
int rt[N];      //求根节点
int vis[N];     //标记数组
int dis[N];     //节点到根节点权值
int ans[N];     //最后答案

void add(int x, int y, int w)
{
    e[cnt].to = y;
    e[cnt].w = w;
    e[cnt].next = head[x];
    head[x] = cnt++;
}
void addask(int u, int v, int index)
{
    ask[num].to = v;
    ask[num].next = h[u];
    ask[num].index = index;
    h[u] = num++;
    ask[num].to = u;
    ask[num].next = h[v];
    ask[num].index = index;
    h[v] = num++;
}
void init()
{
    cnt = num = 0;
    memset(head, -1, sizeof(head));
    memset(h, -1, sizeof(h));
    memset(vis, 0, sizeof(vis));
    memset(rt, 0, sizeof(rt));
    memset(dis, 0, sizeof(dis));
    for (int i = 1; i <= n; i++){
        fa[i] = i;
    }
}
int find(int x)
{
    return fa[x] = fa[x] == x ? x : find(fa[x]);
}

int tarjian(int rt)
{
    for (int i = head[rt]; i != -1; i = e[i].next){
        int x = e[i].to;
        dis[x] = dis[rt] + e[i].w;
        tarjian(x);
        fa[x] = rt;
    }
    vis[rt] = 1;
    for (int i = h[rt]; i != -1; i = ask[i].next){
        int x = ask[i].to;
        if(vis[x]){
            ans[ask[i].index] = dis[rt] + dis[x] - 2 * dis[find(x)];
        }
    }
}
void solve()
{
    int x, y, w, r;
    scanf("%d%d", &n, &m);
    init();
    for (int i = 1; i < n; i++){
        scanf("%d%d%d", &x, &y, &w);
        add(x, y, w);
        rt[y]++;
    }
    for(int i = 1; i <= n; i++){
        if(!rt[i]){
            r = i;  break;
        }
    }
    for (int i = 1; i <= m; i++){
        scanf("%d%d", &x, &y);
        addask(x, y, i);
    }
    tarjian(r);
    for(int i = 1; i <= m; i++){
        printf("%d\n", ans[i]);
    }
}
int main()
{
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}