How far away(倍增LCA)

传送门 HDU2586

题目描述

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.

输入

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,output m lines. Each line represents the answer of the query. Output a bland line after each test case.

样例

  • Input
    2
    3 2
    1 2 10
    3 1 15
    1 2
    2 3

2 2
1 2 100
1 2
2 1

  • Output
    10
    25
    100
    100

题解

  • 题意:给一棵树,求两点的最短距离。
  • 带权LCA。在原有的基础上用dis[i][j]表示节点i到i+(2^j)节点的距离,dis[i][0]就是i节点到父节点的距离,dis[i][j]=dis[i][j-1]+dis[father[i][j-1]][j-1]

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define INIT(a,b) memset(a,b,sizeof(a))
#define LL long long
using namespace std;
const int maxn=4e4+7;
const int maxm=4e4+7;
const int inf=1<<32-1;
int Begin[maxn],fa[maxn][30],dis[maxn][30],lg[maxn],depth[maxn];
struct Edge{
int to,val,next;
}ae[maxn<<1];
int tot=0,n,m;
void Add(int x,int y,int w){
ae[tot]=(Edge){y,w,Begin[x]};
Begin[x]=tot++;
}
void Dfs(int now,int f){
depth[now]=depth[f]+1;
fa[now][0]=f;
for(int i=1;(1<<i)<=depth[now];i++){
fa[now][i]=fa[fa[now][i-1]][i-1];
dis[now][i]=dis[now][i-1]+dis[fa[now][i-1]][i-1];
}
for(int i=Begin[now];~i;i=ae[i].next){
if(ae[i].to!=f){
dis[ae[i].to][0]=ae[i].val;
Dfs(ae[i].to,now);
}
}
}
int Lca(int x,int y){
int ans=0;
if(depth[x]<depth[y]) swap(x,y);
while(depth[x]>depth[y]){
int k=lg[depth[x]-depth[y]]-1;
ans+=dis[x][k];
x=fa[x][k];
}
if(x==y)return ans;
for(int i=lg[depth[x]];i>=0;i--)
if(fa[x][i]!=fa[y][i]){
ans+=dis[x][i];ans+=dis[y][i];
x=fa[x][i],y=fa[y][i];
}
return ans+dis[x][0]+dis[y][0];
}
int main(){
int t;
for(int i=1;i<maxn;i++)
lg[i]=lg[i-1]+(1<<lg[i-1]==i);
scanf("%d",&t);
while(t--){
scanf("%d %d",&n,&m);
INIT(Begin,-1);
int x,y,z;
for(int i=0;i<n-1;i++){
scanf("%d %d %d",&x,&y,&z);
Add(x,y,z);Add(y,x,z);
}
Dfs(1,0);
while(m--){
scanf("%d %d",&x,&y);
printf("%d\n",Lca(x,y));
}
}
return 0;
}
/*
10
15 100
1 2 2
1 3 3
2 4 4
2 5 5
2 6 6
3 7 7
3 8 8
8 9 9
8 10 10
8 11 11
10 12 12
10 13 13
12 14 14
12 15 15
4 15
*/
Donate comment here