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.
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
Source
Recommend
lcy
题意：给一个无根树，有q个询问，问两点之间的距离。
思路：LCA模板题
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define M 100100
using namespace std;
struct node{int w,next,y;}a[4*M];
struct tree{int par[30],dis,dep;}t[4*M];
int head[M*4];
int m,n,l,y,x,k;
char s[100];
void add(int x,int y,int k)
{
a[++l].y=y;a[l].next=head[x];a[l].w=k;head[x]=l;
}
void bt(int x,int fa,int dis)
{ //printf("%d %d %d
",x,fa,dis);
t[x].par[0]=fa;t[x].dis=dis;t[x].dep=t[fa].dep+1;
for(int i=1;(1<<i)<=t[x].dep;i++) t[x].par[i]=t[t[x].par[i-1]].par[i-1];
for(int k=head[x];k;k=a[k].next)
{
int y=a[k].y;
if(!(y==fa)) bt(y,x,dis+a[k].w);
}
}
int lca(int x,int y)
{ int tt;
if(t[x].dep<t[y].dep) {tt=x;x=y;y=tt;}
for(int i=15;i>=0;i--)
if (t[x].dep-t[y].dep>=(1<<i)) x=t[x].par[i];
if(x==y) return x;
for(int i=15;i>=0;i--)
if(!(t[x].par[i]==t[y].par[i])&&(t[x].dep>=(1<<i)))
{
x=t[x].par[i];
y=t[y].par[i];
}
return(t[x].par[0]);
}
void solve()
{
t[0].dep=-1;
bt(1,0,0);
}
int main()
{ int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
//printf("%d%d",n,m);
memset(t[x].par,0,sizeof(t[x].par));l=0;
memset(head,0,sizeof(head));
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&x,&y,&k);
add(x,y,k);add(y,x,k);
}
solve();
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
//printf("%d %d
",t[x].dis,t[y].dis);
int k=lca(x,y);
printf("%d
",t[x].dis+t[y].dis-t[k].dis*2);
}
gets(s);
}
}