HDU-2586(LCA)

How far away ？

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 32298 Accepted Submission(s): 13051

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
           

Source

ECJTU 2009 Spring Contest

題目大意為：先給出一棵樹，然後求出這棵樹中兩個點之間的距離。

解題思路：這道題是一個LCA的模闆題，我們先在給出的樹中先求出該點到根節點的距離，這就相當于一個字首和，然後我們在求出兩個點的最近公共祖先，然後再将兩個結點到根節點的距離相加在減去他們公共祖先到根節點的距離的2倍就得到了這兩個結點之間的距離拉。

代碼：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
const int inf=0x3f3f3f3f;
#define int long long
struct edge
{
    int v,w,next;
}e[maxn];
int cnt,head[maxn];
void add(int a,int b,int c)
{
    e[++cnt]=edge{b,c,head[a]};
    head[a]=cnt;
}
int dis[maxn],fa[maxn][20],lg[maxn],depth[maxn],n,m;
void init()
{
    for(int i=1;i<40010;i++){
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
    }
}
void dfs(int u,int f)
{
    depth[u]=depth[f]+1;
    fa[u][0]=f;
    for(int i=1;i<lg[depth[u]];i++){
        fa[u][i]=fa[fa[u][i-1]][i-1];
    }
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].v,w=e[i].w;
        if(v==f)continue;
        dis[v]=dis[u]+w;
        dfs(v,u);
    }
}
int lca(int a,int b)
{
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    while(depth[a]>depth[b]){
        int k=lg[depth[a]-depth[b]]-1;
        a=fa[a][k];
    }
    if(a==b)return a;
    for(int i=lg[depth[a]]-1;i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i],b=fa[b][i];
        }
    }
    return fa[a][0];
}
void debug()
{
    for(int i=1;i<=n;i++){
        for(int j=0;j<lg[depth[i]];j++)cout<<fa[i][j]<<' ';cout<<endl;
    }
}
signed main()
{
    int t;
    cin>>t;
    init();
    while(t--){
        //int n,m;
        cin>>n>>m;
        //scanf("%d%d",&n,&m);
        memset(head,0,sizeof head);
        //memset(dis,0,sizeof dis);
        cnt=0;
        for(int i=1;i<n;i++){
            int u,v,w;
            cin>>u>>v>>w;
            //scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
        }
        dfs(1,0);
        //debug();
        while(m--){
            int a,b;
            cin>>a>>b;
            //scanf("%d%d",&a,&b);
            int x=lca(a,b);
            //cout<<"lca="<<x<<endl;
            cout<<dis[a]+dis[b]-2*dis[x]<<endl;
        }
    }
}