Hdu 2874(LCA倍增+并查集)

hdu传送门

近似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
/*
Hdu 2586
LCA
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define ms(i,j) memset(i, j, sizeof i);
const int MAXN = 10000 + 5, logs = 21;
struct edge
{
int x, y, c;
}ed[MAXN*2];
int en;
int n, m, c;
vector<int> G[MAXN];
int f[MAXN];//并查集, 判断是否在一棵树
int deep[MAXN], pre[MAXN][logs+1], far[MAXN];//lca
//并查集
int find(int x) {return f[x]==x ? x : f[x] = find(f[x]);}
void merge(int x, int y) {int a = find(x), b = find(y); if (a!=b) f[b] = a;}
//LCA
void dfs(int x, int p)
{
pre[x][0] = p;
for (int i=1;i<=logs;i++) pre[x][i] = pre[pre[x][i-1]][i-1];
for (int i=0;i<G[x].size();i++)
{
int v = ed[G[x][i]].y;
if (v!=p)
{
deep[v] = deep[x] + 1;
far[v] = far[x] + ed[G[x][i]].c;
dfs(v,x);
}
}
}
int lca(int a, int b)
{
if (deep[a]>deep[b]) swap(a,b);
for (int i=logs;i>=0;i--) if (deep[pre[b][i]]>=deep[a]) b = pre[b][i];
if (a==b) return a;
for (int i=logs;i>=0;i--)
if (pre[a][i]!=pre[b][i]) a = pre[a][i], b = pre[b][i];
return pre[a][0];
}
void addedge(int x, int y, int v)
{
en++, ed[en].x = x, ed[en].y = y, ed[en].c = v, G[x].push_back(en);
en++, ed[en].x = y, ed[en].y = x, ed[en].c = v, G[y].push_back(en);
}
void init()
{
for (int i=1;i<=n;i++) f[i] = i, G[i].clear();
en = 0;
for (int i=1;i<=m;i++)
{
int x, y, k;
scanf("%d%d%d", &x, &y, &k);
addedge(x,y,k);
merge(x, y);
}
}
void solve()
{
ms(pre, 0); ms(deep, 0); ms(far, 0);
for (int i=1;i<=n;i++)
if (!deep[i])
{
dfs(i, 0);
}
for (int i=1;i<=c;i++)
{
int x, y;
scanf("%d%d", &x, &y);
if (find(x)!=find(y)) printf("Not connected\n"); else printf("%d\n", far[x]+far[y]-2*far[lca(x,y)]);
}
}
int main()
{
while (scanf("%d%d%d", &n, &m, &c)==3)
{
init();
solve();
}
return 0;
}

------ 本文结束 ------