HDU 2586 How Far Away? LCA水题

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

3 2

1 2 10

3 1 15

1 2

2 3

2 2

1 2 100

1 2

2 1

Sample Output

100

题意：给出一棵树，m个询问

每次询问给出a,b

问a,b的距离。

siz[i] 表示i到根节点的距离

思路：先求出lca=LCA(a,b)

则距离 = siz[a]+siz[b]-2*siz[lca]

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 
  5 using namespace std;
  6 
  7 const int maxn=40000+5;
  8 
  9 struct Edge
 10 {
 11     int to,next,w;
 12 }edge[maxn<<1];
 13 int head[maxn];
 14 int tot;
 15 int p[maxn][24];
 16 int siz[maxn];
 17 int dep[maxn];
 18 
 19 void init(int n)
 20 {
 21     tot=1;
 22     memset(head,-1,sizeof(head));
 23     memset(siz,0,sizeof(siz));
 24     memset(dep,0,sizeof(dep));
 25 
 26     for(int i=1;i<=n;i++)
 27         for(int j=0;j<24;j++)
 28             p[i][j]=-1;
 29 }
 30 
 31 void addedge(int u,int v,int w)
 32 {
 33     edge[tot].to=v;
 34     edge[tot].w=w;
 35     edge[tot].next=head[u];
 36     head[u]=tot++;
 37 }
 38 
 39 void dfs(int n,int u,int fa)
 40 {
 41     for(int i=head[u];~i;i=edge[i].next)
 42     {
 43         int v=edge[i].to;
 44         int w=edge[i].w;
 45         if(!dep[v]&&v!=fa)
 46         {
 47             dep[v]=dep[u]+1;
 48             p[v][0]=u;
 49             siz[v]=siz[u]+w;
 50             dfs(n,v,u);
 51         }
 52     }
 53 }
 54 
 55 void init_lca(int n)
 56 {
 57     for(int j=1;(1<<j)<=n;j++)
 58     {
 59         for(int i=1;i<=n;i++)
 60         {
 61             if(p[i][j-1]!=-1)
 62             {
 63                 p[i][j]=p[p[i][j-1]][j-1];
 64             }
 65         }
 66     }
 67 }
 68 
 69 int solve(int n,int u,int v)
 70 {
 71     if(u==v)
 72         return 0;
 73     if(dep[u]<dep[v])
 74     {
 75         swap(u,v);
 76     }
 77 
 78     int init_u=u;
 79     int init_v=v;
 80 
 81     int cnt;
 82     for(cnt=0;(1<<cnt)<=dep[u];cnt++)
 83         ;
 84     cnt--;
 85 
 86     for(int j=cnt;j>=0;j--)
 87     {
 88         if(dep[u]-(1<<j)>=dep[v])
 89             u=p[u][j];
 90     }
 91 
 92     if(u==v)
 93         return (siz[init_u]-siz[u]);
 94 
 95     for(int j=cnt;j>=0;j--)
 96     {
 97         if(p[u][j]!=-1&&p[u][j]!=p[v][j])
 98         {
 99             u=p[u][j];
100             v=p[v][j];
101         }
102     }
103     int lca=p[u][0];
104 
105     return (siz[init_u]+siz[init_v]-2*siz[lca]);
106 
107 }
108 
109 int main()
110 {
111     int test;
112     scanf("%d",&test);
113 
114     while(test--)
115     {
116         int n,m;
117         scanf("%d%d",&n,&m);
118 
119         init(n);
120 
121         for(int i=1;i<n;i++)
122         {
123             int u,v,w;
124             scanf("%d%d%d",&u,&v,&w);
125             addedge(u,v,w);
126             addedge(v,u,w);
127         }
128 
129         dfs(n,1,-1);
130         init_lca(n);
131 
132         /*
133         for(int i=1;i<=n;i++)
134             printf("%d
",siz[i]);
135         */
136 
137         for(int i=1;i<=m;i++)
138         {
139             int u,v;
140             scanf("%d%d",&u,&v);
141             //printf("eee
");
142             printf("%d
",solve(n,u,v));
143         }
144     }
145 
146     return 0;
147 }

31ms