CD操作 【LCA树上倍增】

题目链接HUD-4547


题目描述

在Windows下我们可以通过cmd运行DOS的部分功能,其中CD是一条很有意思的命令,通过CD操作,我们可以改变当前目录。
  这里我们简化一下问题,假设只有一个根目录,CD操作也只有两种方式:
  
  1. CD 当前目录名...\目标目录名 (中间可以包含若干目录,保证目标目录通过绝对路径可达)
  2. CD .. (返回当前目录的上级目录)
  
  现在给出当前目录和一个目标目录,请问最少需要几次CD操作才能将当前目录变成目标目录?


思路

分两种情况讨论,当要查询的a,b直接是祖先关系。
若b是a的祖先,则直接输出两个节点的深度差即可;
其他情况,找到最近公共祖先,然后到达公共祖先需要深度差步,然后再往下1步即可到达;

这里给出的字符串,我用的是string处理,没出现过的string赋新值,出现过则直接用;

PS:测试数据可能有锅? 他说了边数应该是N-1,1e5的数据范围,然后双向边,我开了2e5竟然RE,迷;
开了4e5才过;

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

#define MAX_N 100010
#define MAX_M 200010

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

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

void init()
{
for(int i = 1; i <= n; i++)
pre[i] = i;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
}

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

int Find(int x)
{
return x == pre[x] ? pre[x] : pre[x] = Find(pre[x]);
}

void Union(int x, int y)
{
x = Find(x);
y = Find(y);
if(x != y)
pre[x] = y;
}

void dfs(int u)
{
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(!dfn[v])
{
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()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--)
{
int ans = 1;
string x, y;
map<string, int> F;
cin >> n >> m;
init();
for(int i = 0; i < n - 1; i++)
{
cin >> x >> y;
if(!F[x])
{
F[x] = ans++;
}
if(!F[y])
{
F[y] = ans++;
}
Union(F[x], F[y]);
add(F[x], F[y]);
add(F[y], F[x]);
}
int r = Find(pre[F[x]]);
fa[r][0] = 0, dfn[r] = 1;
dfs(r);
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--)
{
string x, y;
cin >> x >> y;
if(lca(F[x], F[y]) != F[y])
cout << dfn[F[x]] - dfn[lca(F[x], F[y])] + 1 << endl;
else
{
cout << dfn[F[x]] - dfn[F[y]] << endl;
}
}
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------