HDU - 2586 How far away ？

Posted on | In ,

思路

模板题，保存DFS序后使用RMQ求LCA。这个算法相对来说比较好理解。我们访问的顺序是类似根-子节点-根的顺序，记录访问顺序后使用RMQ查询两点之间depth的最小值就是LCA。这题我真的是无限RE,最后发现是自己ST表的模板有问题。。

代码

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 <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#include <complex>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1) 
#define rson(x) (x<<1+1)
#define sqr(x) ((x)*(x))

using namespace std;

const int MAX_V = 40010,MAX_LOG_V=25;
vector<pair<int,int>> G[MAX_V];
int root,n,m;
int vis[MAX_V];
int vs[MAX_V * 2 ];
int depth[MAX_V * 2];
int id[MAX_V];
int dist[MAX_V];
void dfs(int v, int p, int d, int &k) {
	id[v] = ++k;
	vis[v] = 1;
	vs[k] = v;
	depth[k] = d;
	for (int i = 0;i < G[v].size();i++) {
		if (!vis[G[v][i].first]) {
			dist[G[v][i].first] = dist[v] + G[v][i].second;
			dfs(G[v][i].first, v, d + 1, k);
			vs[++k] = v;
			depth[k] = d;
		}
	}
}
int dp[2*MAX_V][MAX_LOG_V];
void ST(int len)
{
	int K = (int)(log((double)len) / log(2.0));
	for (int i = 1; i <= len; i++) dp[i][0] = i;
	for (int j = 1; j <= K; j++)
		for (int i = 1; i +(1<<j)- 1 <= len; i++)
		{
			int a = dp[i][j - 1], b = dp[i + (1<<(j-1))][j - 1];
			if (depth[a] < depth[b]) dp[i][j] = a;
			else            dp[i][j] = b;
		}
}

int RMQ(int x, int y)
{
	int K = (int)(log((double)(y - x + 1)) / log(2.0));
	int a = dp[x][K], b = dp[y - (1<<K) + 1][K];
	if (depth[a] < depth[b]) return a;
	else            return b;
}

int LCA(int u, int v)
{
	int x = id[u], y = id[v];
	if (x > y) swap(x, y);
	int res = RMQ(x, y);
	return vs[res];
}
int main(){
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t,u,v,val;
	cin >> t;
	while (t--) {
		for (int i = 0;i < MAX_V;i++)G[i].clear();
		ms(vs, 0), ms(depth, 0), ms(id, 0), ms(id, 0), ms(dist, 0),ms(vis,0),ms(dp,0);
		cin >> n >> m;
		for (int i = 0;i < n - 1;i++) {
			cin >> u >> v >> val;
			G[u].push_back(make_pair(v, val)), G[v].push_back(make_pair(u, val));
		}
		int k = 0;
		dfs(1, -1, 0, k);
		ST(n* 2 - 1);
		for (int i = 0;i < m;i++) {
			cin >> u >> v;
			int z = LCA(u, v);
			cout << dist[u] + dist[v] - 2 * dist[z]<<"\n";
		}
	}
	return 0;
}