Skip to content

Codeforces - 1675D. Vertical Paths

检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

#题面

本文中所给出的题面为原题面的中文翻译,并非原始题面。翻译如有错误之处,请联系指出。

#题目描述

给定一棵由 nn 个顶点组成的有根树。顶点由 11nn 编号。任何顶点都可以是树的根。

请在树上找出这样一组路径:

  • 每个顶点恰好属于一条路径,每条路径可以包含一个或多个顶点;
  • 在每条路径中,每个节点的下一个节点是当前节点的子节点(即路径总是向下 —— 从父节点到子节点);
  • 路径的数量最少。

#输入格式

第一行输入一个整数 tt 表示该测试点内测试数据的组数。

每组测试点的第 11 行包含一个整数 nn 表示树的节点个数。第 22 行包含 nn 个整数,第 ii 个整数 pip_i 表示第 ii 个节点的父节点为 pip_i。根节点的父亲是它本身。

#输出格式

对于每组测试数据:

11 行输出一个整数 mm 表示组内路径的数量。

然后输出 mm 条路径的信息:

  • 11 行输出路径的长度;
  • 22 行按照从上到下的顺序输出该路径内的的所有节点编号。

在每组测试数据的末尾输出一个空行。

如果有多种答案,输出其中的任何一种即可。

#输入输出样例

输入样例 #1

6
5
3 1 3 3 1
4
1 1 4 1
7
1 1 2 3 4 5 6
1
1
6
4 4 4 4 1 2
4
2 2 2 2

输出样例 #1

3
3
3 1 5
1
2
1
4

2
2
1 2
2
4 3

1
7
1 2 3 4 5 6 7

1
1
1

3
3
4 1 5
2
2 6
1
3

3
2
2 1
1
3
1
4

样例解释 #1

以该测试点中的第一组数据为例,有三条路径:

  • 3153 \rarr 1 \rarr 5,长度为 33
  • 44,长度为 11
  • 22,长度为 11

#数据范围与约定

对于 100%100\% 的数据,1t1041 \leq t \leq 10^41n2×1051 \leq n \leq 2 \times 10^51pin1 \leq p_i \leq n

数据保证每个测试点中的所有测试数据中 nn 的总和不超过 2×1052 \times 10^5

#思路

看到这道题的样例说明之后第一眼想到的是树链剖分(图源 OI Wiki):

按照这样剖出来的答案显然是对的。

再看看样例会发现一个很显然的结论:最小路径数一定是叶子节点数。

可以使用深度优先搜索,遇到分叉的时候就新开其他路径,同时挑选一个方向继续当前路径,这样出来的答案一定是最优的。

具体实现可以看代码。

#代码

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
#include <iostream>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int t, n, fa[N], root, ans_cnt;
std::vector<int> g[N], ans[N];

void dfs(int u, int fa, int cnt) {
if (g[u].size() == 1) { // 是否是叶子节点
ans[cnt].push_back(u);
return;
}

ans[cnt].push_back(u);

bool f = false;

for (int v : g[u]) {
if (v == fa) continue;

if (!f) {
dfs(v, u, cnt);
f = true;
} else {
dfs(v, u, ++ans_cnt);
}
}
}

int main() {
std::ios::sync_with_stdio(false);

cin >> t;

while (t--) {
root = 0;
ans_cnt = 1;

cin >> n;

for (int i = 1; i <= n; i++) {
cin >> fa[i];

if (fa[i] == i) root = i;

g[i].push_back(fa[i]);
g[fa[i]].push_back(i);
}

dfs(root, root, 1);

for (int i = 1; i <= n; i++) {
g[i].clear();
}

cout << ans_cnt << endl;
for (int i = 1; i <= ans_cnt; i++) {
cout << ans[i].size() << endl;
for (int x : ans[i]) {
cout << x << ' ';
}
cout << endl;

ans[i].clear();
}
cout << endl;
}

return 0;
}