How far away ? 【LCA树上倍增】

题目链接HDU-2586


题目描述

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.
就是给你一颗树,然后问任意两点的距离是多少;


思路

一开始看到数据范围只有40000,想着爆搜也不会T掉,然后就写了一发爆搜,然后就过了;

爆搜代码

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
#include <bits/stdc++.h>
using namespace std;

#define MAX_N 40010

int head[MAX_N], cnt = 0, vis[MAX_N], sum = 0;
int n, m;

struct Node{
int to, val, next;
}edge[MAX_N * 2];

void init()
{
memset(head, -1, sizeof(head));
cnt = sum = 0;
}

void add(int x, int y, int val)
{
edge[cnt].to = y;
edge[cnt].val = val;
edge[cnt].next = head[x];
head[x] = cnt++;
}

int dfs(int x, int y)
{
for(int i = head[x]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(v == y)
{
return edge[i].val;
}
else
{
if(!vis[v])
{
vis[v] = 1;
int k = dfs(v, y);
if(k)
return edge[i].val + k;
}
}
}
return 0;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
init();
cin >> n >> m;
for(int i = 0; i < n - 1; i++)
{
int x, y, val;
cin >> x >> y >> val;
add(x, y, val);
add(y, x, val);
}
while(m--)
{
memset(vis, 0, sizeof(vis));
int x, y;
cin >> x >> y;
vis[x] = 1;
cout << dfs(x, y) << endl;
}
}
return 0;
}

爆搜的意思就是从x点出发,能不能到达y点,可以到达则返回到达y点的距离,不能到达那就返回0,由于是无向图,所以加了一个vis数组记录节点是否已经访问;可能数据比较弱吧,然后就是用LCA的解法;

LCA是用来求解最近公共祖先的,在这道体中,我们可以在dfs预处理的时候把每个节点到根节点的距离也预处理出来;就是 Dist[v] = Dist[u] + edge[i].val;
这样子;
然后画张图看一下;
在这里插入图片描述
若我们要求4到6的距离,则只需要求出4,6的最近公共祖先,也就是3;
然后Dist[4] + Dist[6] - 2 * Dist[3] 就是4到6的距离了;很好理解的;

LCA代码

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 500050
#define MAX_M 500050

int head[MAX_N], cnt = 0, fa[MAX_N][30], dfn[MAX_N], Dist[MAX_N];
int n, m, t;

struct Node{
int to, val, next;
}edge[MAX_M * 2];

void init()
{
cnt = 0;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
}

void add(int x, int y, int val)
{
edge[cnt].to = y;
edge[cnt].val = val;
edge[cnt].next = head[x];
head[x] = cnt++;
}

void dfs(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(!dfn[v])
{
Dist[v] = Dist[u] + edge[i].val;
dfn[v] = dfn[u] + 1;
fa[v][0] = u;
dfs(v);
}
}
}

int lca(int x, int y)
{
if(dfn[x] < dfn[y])
{
swap(x, y);
}
for(int i = 20; i >= 0; i--)
{
if(dfn[fa[x][i]] >= dfn[y])
{
x = fa[x][i];
}
}
if(x == y)
return x;
for(int i = 20; i >= 0; i--)
{
if(fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
}
}
return fa[x][0];
}

int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d %d", &n, &m);
init();
for(int i = 0; i < n - 1; i++)
{
int x, y, val;
scanf("%d %d %d", &x, &y, &val);
add(x, y, val);
add(y, x, val);
}
dfn[1] = 1, fa[1][0] = 0, Dist[1] = 0;
dfs(1);
for(int i = 1; i <= 20; i++)
{
for(int j = 1; j <= n; j++)
{
fa[j][i] = fa[fa[j][i-1]][i-1];
}
}
while(m--)
{
int x, y;
scanf("%d %d", &x, &y);
printf("%d\n", Dist[x] + Dist[y] - 2 * Dist[lca(x, y)]);
}
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------