HDU2586 | HDU2586

最近的共同祖先反复问的问题。
#include <iostream>

#include <algorithm>

#include <vector>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 40000 + 10;

struct Edge{

   int to,cost;

   Edge(){};

   Edge(int _to,int _cost)

      :to(_to),cost(_cost){};

};

vector<Edge> tree[MAXN];

vector<Edge> Qes[MAXN];

int degree[MAXN];

int f[MAXN];

bool vst[MAXN];

int dist[MAXN];

int ancestor[MAXN];

int ans[MAXN];

int rank[MAXN];

int N,M;

void init(){

    for(int i = 0;i <= N;++i){

        degree[i] = 0;

        f[i] = i;

        ans[i] = -1;

        rank[i] = 0;

        dist[i] = 0;

        vst[i] = false;

        ancestor[i] = -1;

        tree[i].clear();

        Qes[i].clear();

    }

}

int Find(int x){

    if(x == f[x])

        return x;

    return f[x] = Find(f[x]);

}

void LCA(int u){

    int sz = tree[u].size();

    for(int i = 0;i < sz;++i){

        Edge& e = tree[u][i];

        if(!vst[e.to]){

            vst[e.to] = 1;

            dist[e.to] = dist[u] + e.cost;

            LCA(e.to);

            f[e.to] = u;

            int k = Qes[e.to].size();

            for(int j = 0;j < k;++j){

                Edge& et = Qes[e.to][j];

                if(vst[et.to]&&ans[et.cost] == -1){  //还未遍历到

                    if(et.to == e.to) ans[et.cost] = 0;

                    else ans[et.cost] = dist[e.to] + dist[et.to] - 2*dist[Find(et.to)];

                }

            }

        }

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&M);

        init();

        int x,y,c;

        for(int i = 1;i < N;++i){

            scanf("%d%d%d",&x,&y,&c);

            tree[x].push_back(Edge(y,c));

            tree[y].push_back(Edge(x,c));

        }

        for(int i = 0;i < M;++i){

            scanf("%d%d",&x,&y);

            Qes[x].push_back(Edge(y,i));

            Qes[y].push_back(Edge(x,i));

        }

        vst[1] = 1;

        LCA(1);

        for(int i = 0;i < M;++i){

            printf("%d\n",ans[i]);

        }

    }

    return 0;

}