How far away ？
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 14685 Accepted Submission(s): 5554
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
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
25
100
100
Source
题意:给你一颗带权树 求任意两个结点间的最短距离
题解:dis存结点到根的距离+lca dis=dis[a]+dis[b]-2*dis[lca(a,b)]; 倍增法求lca
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <map>
#define ll __int64
#define mod 1000000007
#define dazhi 2147483647
#define bug() printf("!!!!!!!")
using namespace std;
#define maxn 40010
#define M 22
struct node
{
int pre;
int to;
int w;
}N[maxn*];
int pre[maxn];
int deep[maxn],nedge=;
int dis[maxn];
int rudu[maxn];
int fa[maxn][M];
int t;
int f1,t1,w1;
int l,r;
int n,m;
void add(int from ,int to,int ww)
{
nedge++;
N[nedge].to=to;
N[nedge].pre=pre[from];
N[nedge].w=ww;
pre[from]=nedge;
}
void dfs(int u)
{
for(int i=pre[u];i;i=N[i].pre)
{
int v=N[i].to;
if(deep[v]==)
{
dis[v]=dis[u]+N[i].w;
deep[v]=deep[u]+;
fa[v][]=u;
dfs(v);
}
}
}
void st(int n)
{
for(int j=;j<M;j++)
for(int i=;i<=n;i++)
fa[i][j]=fa[fa[i][j-]][j-];
}
int lca(int u,int v)
{
if(deep[u]<deep[v]) swap(u,v);
int d=deep[u]-deep[v];
int i;
for(i=;i<M;i++)
{
if((<<i)&d)
{
u=fa[u][i];
}
}
if(u==v) return u;
for(i=M-;i>=;i--)
{
if(fa[u][i]!=fa[v][i])
{
u=fa[u][i];
v=fa[v][i];
}
}
u=fa[u][];
return u;
}
void init()
{
memset(rudu,,sizeof(rudu));
memset(dis,,sizeof(dis));
memset(deep,,sizeof(deep));
memset(fa,,sizeof(fa));
memset(N,,sizeof(N));
memset(pre,,sizeof(pre));
nedge=;
}
int main()
{
while(scanf("%d",&t)!=EOF)
{
for(int i=;i<=t;i++)
{
init();
scanf("%d %d",&n,&m);
for(int j=;j<n;j++)
{
scanf("%d %d %d",&f1,&t1,&w1);
add(f1,t1,w1);
rudu[t1]++;
}
for(int j=;j<=n;j++)
{
if(rudu[j]==)
{
deep[j]=;
dis[j]=;
dfs(j);
break;
}
}
st(n);
for(int j=;j<=m;j++)
{
int aa,bb;
scanf("%d %d",&aa,&bb);
printf("%d\n",dis[aa]+dis[bb]-*dis[lca(aa,bb)]);
}
}
}
return ;
}