发布于 

商务旅行

商务旅行(LCA)

Code[VS] 1036

这也是一道模板题了,这个博客也还没写过LCA的题目,整理板子时又写了两遍,顺便发上来吧。

题目来源: Code[VS]

倍增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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>

#define MAXN 500100
#define INF 0x3f3f3f3f

using namespace std;

struct Edge *f[MAXN];
int fa[MAXN][22];
int val[20];
int depth[MAXN];
int n;

struct Edge
{
int from, to;
Edge *next;

Edge(int from = 0, int to = 0):
from(from), to(to), next(f[from]) {}

~Edge()
{
delete next;
}
};

queue<int> q;
void bfs(int s)
{
memset(depth, INF, sizeof(depth));
depth[0] = 0;
depth[s] = 1;
q.push(s);
while (!q.empty())
{
int tmp = q.front(); q.pop();
for (Edge *e = f[tmp]; e; e = e->next)
{
if (depth[e->to]==INF)
{
depth[e->to] = depth[tmp] + 1;
q.push(e->to);

fa[e->to][0] = tmp;
}
}
}
}

void init()
{
val[0] = 1;
for (int i = 1; i<=20; i++)
{
val[i] = val[i-1] * 2;
}

for (int j = 1; j<=20; j++)
for (int i = 1; i<=n; i++)
{
fa[i][j] = fa[ fa[i][j-1] ][j-1];
}
}

int LCA(int x, int y)
{
int ans = 0;
if (depth[x] < depth[y])
swap(x, y);

for (int i = 20; depth[x]>depth[y]; i--)
if (depth[ fa[x][i] ] >= depth[y])
{
ans += val[i];
x = fa[x][i];
}

if (x==y)
return ans;

for (int i = 20; i>=0; i--)
if (fa[x][i] != fa[y][i])
{
x = fa[x][i];
y = fa[y][i];
ans += val[i]*2;
}

ans += 2;
return ans;
}

int main()
{
memset(fa, 0, sizeof(fa));
memset(f, 0, sizeof(f));

cin >> n;

for (int i = 1; i<n; i++)
{
int x, y;
cin >> x >> y;

f[x] = new Edge(x, y);
f[y] = new Edge(y, x);
}

bfs(1);
init();

int ans = 0;

int m;
cin >> m;
int x;
cin >> x;
for (int i = 1; i<m; i++)
{
int y;
cin >> y;
ans += LCA(x, y);

x = y;
}

cout << ans << endl;
}

Tarjan 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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <queue>

#define MAXN 30100

using namespace std;

struct Edge *f[MAXN];
struct Edge
{
int from, to;
Edge *next, *oppo;
bool access;

Edge(int from=0, int to=0)
:from(from), to(to), next( f[from] ) {access=true;}
};

struct Query
{
int node;
Query *next;

Query(int node = 0, Query *next = NULL)
:node(node), next(next) {}
};
Query *query[MAXN];
int depth[MAXN], fa[MAXN];
bool flag[MAXN];
int ans;

queue<int> q;
void bfs(int s)
{
depth[s] = 1;
q.push(s);
while (!q.empty())
{
int tmp = q.front();
q.pop();

for (Edge *e = f[tmp]; e; e = e->next)
if (e->access)
{
e->oppo->access = false;
depth[e->to] = depth[tmp] + 1;
q.push(e->to);
}
}
}

int find(int x)
{
return fa[x]==x? x : fa[x] = find(fa[x]);
}

void Union(int x, int y)
{
int fy = find(y);
fa[fy] = x;
}

void Tarjan(int x)
{
fa[x] = x;

for (Edge *e = f[x]; e; e = e->next)
if (e->access)
{
Tarjan(e->to);
Union(x, e->to);
}

flag[x] = true;

for (Query *q = query[x]; q; q = q->next)
{
if (flag[ q->node ])
ans += depth[x] + depth[ q->node ] - 2 * depth[ find( q->node )];
}
}

int main()
{
int n;
cin >> n;

for (int i = 1; i<n; i++)
{
int x, y;
cin >> x >> y;
f[x] = new Edge(x, y);
f[y] = new Edge(y, x);

f[x]->oppo = f[y];
f[y]->oppo = f[x];
}

int m;
cin >> m;
int x;
cin >> x;
for (int i = 1; i<m; i++)
{
int y;
cin >> y;

query[x] = new Query(y, query[x]);
query[y] = new Query(x, query[y]);

x = y;
}

bfs(1);
Tarjan(1);

cout << ans << endl;
}

本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。

本站由 [@Songer](https://blog.songer.xyz/) 创建,使用 Stellar 作为主题。