HDU2586

HDU2586

一道多次詢問的最近公共祖先問題。

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 40000 + 10;
struct Edge{
   int to,cost;
   Edge(){};
   Edge(int _to,int _cost)
      :to(_to),cost(_cost){};
};

vector tree[MAXN];
vector 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;
}