hdu-2586-How far away ？(离线LCA)-白红宇

hdu-2586-How far away ？(离线LCA)

阅读量：5101 次

发布时间：2019-06-13

本文共 2061 字，大约阅读时间需要 6 分钟。

题意：

给定一棵树，每条边都有一定的权值，q次询问，每次询问某两点间的距离。

分析：

这样就可以用LCA来解，首先找到u, v 两点的lca，然后计算一下距离值就可以了。

这里的计算方法是，记下根结点到任意一点的距离dis[]，这样ans = dis[u] + dis[v] - 2 * dis[lca(v, v)]。

// File Name: 2586.cpp// Author: Zlbing// Created Time: 2013年08月19日 星期一 10时59分47秒#pragma comment(linker,"/STACK:102400000,102400000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 using namespace std;#define CL(x,v); memset(x,v,sizeof(x));#define INF 0x3f3f3f3f#define LL long long#define REP(i,r,n) for(int i=r;i<=n;i++)#define RREP(i,n,r) for(int i=n;i>=r;i--)const int MAXN=4e4+100;struct Edge{ int u,v,cost; Edge() { } Edge(int u,int v,int cost):u(u),v(v),cost(cost) { }};vector
                 
                   edges;vector
                  
                    qedges;vector
                   
                     G[MAXN],Q[MAXN];int vis[MAXN];int dis[MAXN];int in[MAXN];int f[MAXN];int find(int x){ return f[x]==x?x:f[x]=find(f[x]);}void LCA(int u,int fa){ for(int i=0;i<(int)G[u].size();i++) { Edge e=edges[G[u][i]]; if(e.v==fa)continue; dis[e.v]=dis[u]+e.cost; LCA(e.v,u); f[find(e.v)]=u; } vis[u]=1; for(int i=0;i<(int)Q[u].size();i++) { Edge& e=qedges[Q[u][i]]; if(vis[e.v]) { int ancestor=find(e.v); qedges[Q[u][i]].cost=dis[e.v]+dis[e.u]-2*dis[ancestor]; } }}int main(){ int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); REP(i,1,n) { G[i].clear(); Q[i].clear(); vis[i]=0; dis[i]=0; in[i]=0; f[i]=i; } edges.clear(); qedges.clear(); int a,b,c; REP(i,1,n-1) { scanf("%d%d%d",&a,&b,&c); in[b]++; edges.push_back(Edge(a,b,c)); edges.push_back(Edge(b,a,c)); int mm=edges.size(); G[a].push_back(mm-2); G[b].push_back(mm-1); } REP(i,1,m) { scanf("%d%d",&a,&b); qedges.push_back(Edge(a,b,-1)); qedges.push_back(Edge(b,a,-1)); int mm=qedges.size(); Q[a].push_back(mm-2); Q[b].push_back(mm-1); } for(int i=1;i<=n;i++) { if(!in[i]) LCA(i,-1); } for(int i=0;i<(int)qedges.size();i++) { Edge e=qedges[i]; if(e.cost!=-1) { printf("%d\n",e.cost); } } } return 0;}