3555. 二叉树
摘要
Title: 3555. 二叉树
Tag: lca
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3555. 二叉树
-
题意
给定一个 n 个结点（编号 1∼n）构成的二叉树，其根结点为 1 号点。
进行 m 次询问，每次询问两个结点之间的最短路径长度。
树中所有边长均为 1。 -
思路
总体思路就是，求出所有结点到根节点的距离，再求出两个点的lca，用距离之和减去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/*
* @Author: NEFU AB-IN
* @Date: 2022-08-04 09:00:27
* @FilePath: \Acwing\3555\3555.cpp
* @LastEditTime: 2022-08-04 09:29:12
*/
using namespace std;
typedef pair<int, int> PII;
const int INF = INT_MAX;
const int N = 1e6 + 10;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> g[n + 1], depth(n + 1), st(n + 1);
vector<vector<int>> fa(n + 1, vector<int>(11)); // 因为n只有1000，所以指数开到10就够用
for (int i = 1; i <= n; ++i)
{
int ls, rs;
cin >> ls >> rs;
if (ls != -1)
g[i].push_back(ls);
if (rs != -1)
g[i].push_back(rs);
}
function<void(int)> bfs = [&](int root) {
queue<int> q;
q.push(root);
//初始化depth
depth[0] = 0; // 哨兵，用来防止越界，代表0的深度为0
depth[root] = 1;
st[root] = 1;
while (SZ(q))
{
auto t = q.front();
q.pop();
for (auto v : g[t])
{
if (!st[v])
{
st[v] = 1;
depth[v] = depth[t] + 1;
fa[v][0] = t; // fa数组初始化，v向上跳2的0次方，就是父节点，也就是t
for (int k = 1; k <= 10; ++k) // v向上跳2的k次方，也就是先跳2的k-1次方，再跳2的k-1次方
{
fa[v][k] = fa[fa[v][k - 1]][k - 1];
}
q.push(v);
}
}
}
};
function<int(int, int)> lca = [&](int a, int b) {
if (depth[a] < depth[b]) // 让a成为要跳的那个
swap(a, b);
for (int k = 10; k >= 0; --k) // 开始往上跳，跳到和b同一层
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) // 如果这时候相等了，说明b就是lca
return a;
// 否则一起往上跳，跳到他们的lca的下一层
for (int k = 10; k >= 0; --k)
{
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
}
// 返回父节点即可
return fa[a][0];
};
bfs(1);
for (int i = 1; i <= m; ++i)
{
int x, y;
cin >> x >> y;
cout << depth[x] + depth[y] - 2 * depth[lca(x, y)] << '\n';
}
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}无注释版
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/*
* @Author: NEFU AB-IN
* @Date: 2022-08-04 09:00:27
* @FilePath: \Acwing\3555\3555.cpp
* @LastEditTime: 2022-08-04 09:29:12
*/
using namespace std;
typedef pair<int, int> PII;
const int INF = INT_MAX;
const int N = 1e6 + 10;
void solve()
{
int n, m;
cin >> n >> m;
vector<int> g[n + 1], depth(n + 1), st(n + 1);
vector<vector<int>> fa(n + 1, vector<int>(11));
for (int i = 1; i <= n; ++i)
{
int ls, rs;
cin >> ls >> rs;
if (ls != -1)
g[i].push_back(ls);
if (rs != -1)
g[i].push_back(rs);
}
function<void(int)> bfs = [&](int root) {
queue<int> q;
q.push(root);
//初始化depth
depth[0] = 0; // 哨兵
depth[root] = 1;
st[root] = 1;
while (SZ(q))
{
auto t = q.front();
q.pop();
for (auto v : g[t])
{
if (!st[v])
{
st[v] = 1;
depth[v] = depth[t] + 1;
fa[v][0] = t;
for (int k = 1; k <= 10; ++k)
{
fa[v][k] = fa[fa[v][k - 1]][k - 1];
}
q.push(v);
}
}
}
};
function<int(int, int)> lca = [&](int a, int b) {
if (depth[a] < depth[b])
swap(a, b);
for (int k = 10; k >= 0; --k)
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b)
return a;
for (int k = 10; k >= 0; --k)
{
if (fa[a][k] != fa[b][k])
{
a = fa[a][k];
b = fa[b][k];
}
}
return fa[a][0];
};
bfs(1);
for (int i = 1; i <= m; ++i)
{
int x, y;
cin >> x >> y;
cout << depth[x] + depth[y] - 2 * depth[lca(x, y)] << '\n';
}
return;
}
signed main()
{
IOS;
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
