hduP2586——How far away ？

Problem Description

There are n houses in the village and some bidirectional roads connecting them. Every day peole always like to ask like this "How far is it if I want to go from house A to house B"? Usually it hard to answer. But luckily int this village the answer is always unique, since the roads are built in the way that there is a unique simple path("simple" means you can't visit a place twice) between every two houses. Yout task is to answer all these curious people.

Input

First line is a single integer T(T<=10), indicating the number of test cases.
For each test case,in the first line there are two numbers n(2<=n<=40000) and m (1<=m<=200),the number of houses and the number of queries. The following n-1 lines each consisting three numbers i,j,k, separated bu a single space, meaning that there is a road connecting house i and house j,with length k(0<k<=40000).The houses are labeled from 1 to n.
Next m lines each has distinct integers i and j, you areato answer the distance between house i and house j.

Output

For each test case,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

Sample Input

2 3 2 1 2 10 3 1 15 1 2 2 3 2 2 1 2 100 1 2 2 1

Sample Output

10 25 100 100

最简单的LCA，用d[u]存u到根节点距离，然后u到v的距离就为他们的d[i]减去2被的祖先的d[i]

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 using namespace std;
  5 const int maxn=80005;
  6 int head[maxn],tov[maxn],w[maxn],nextn[maxn];
  7 int fa[maxn][16],deep[maxn];
  8 int dis[maxn];
  9 bool pd[maxn];
 10 int tot=0;
 11 int xxx;
 12 void go(int x,int y,int z)
 13 {
 14     tot++;
 15     nextn[tot]=head[x];
 16     head[x]=tot;
 17     tov[tot]=y;
 18     w[tot]=z;
 19 }
 20 void dfs(int x)
 21 {
 22     int v=head[x];
 23     while(v)
 24     {
 25         if(pd[tov[v]]==false)
 26         {
 27             pd[tov[v]]=true;
 28             deep[tov[v]]=deep[x]+1;
 29             dis[tov[v]]=dis[x]+w[v];
 30             fa[tov[v]][0]=x;
 31             int ii=0,po=x;
 32             while(fa[po][ii]!=0)
 33             {
 34                 fa[tov[v]][ii+1]=fa[po][ii];
 35                 po=fa[po][ii];
 36                 ii++;
 37             }
 38             dfs(tov[v]);
 39         }
 40         v=nextn[v];
 41     }
 42 }
 43 int lca(int x,int y)
 44 {
 45     if(x==y)
 46     return x;
 47     if(deep[x]<deep[y]){int t=x;x=y;y=t;}
 48     int m=deep[x]-deep[y];
 49     int ii=0;
 50     while(m!=0)
 51     {
 52         if(m&1==1)
 53         x=fa[x][ii];
 54         m=(m>>1);
 55         ii++;
 56     }
 57     ii=0;
 58     while(x!=y)
 59     {
 60         if(fa[x][ii]!=fa[y][ii]||(fa[x][ii]==fa[y][ii]&&(ii==0)))
 61         {
 62             x=fa[x][ii];y=fa[y][ii];
 63             ii++;
 64         }
 65         else ii--;
 66     }
 67     return x;
 68 }
 69 
 70 int main()
 71 {
 72     scanf("%d",&xxx);
 73     for(int i=1;i<=xxx;i++)
 74     {
 75         memset(head,0,sizeof(head));
 76         memset(nextn,0,sizeof(nextn));
 77         memset(tov,0,sizeof(tov));
 78         memset(w,0,sizeof(w));
 79         memset(fa,0,sizeof(fa));
 80         memset(deep,0,sizeof(deep));
 81         memset(pd,0,sizeof(pd));
 82         memset(dis,0,sizeof(dis));
 83         
 84         int n,m;
 85         scanf("%d%d",&n,&m);
 86         for(int i=1;i<=n-1;i++)
 87         {
 88             int x,y,z;
 89             scanf("%d%d%d",&x,&y,&z);
 90              go(x,y,z);go(y,x,z);
 91         }
 92         deep[1]=1;
 93         pd[1]=true;
 94         dfs(1);
 95         for(int i=1;i<=m;i++)
 96         {
 97             int x,y;
 98             scanf("%d%d",&x,&y);
 99             printf("%d
",dis[x]+dis[y]-2*dis[lca(x,y)]);
100         }
101     }
102     return 0;
103 }