一道多次询问的最近公共祖先问题。

#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; }