Skip to content

Codeforces - 1675D. Vertical Paths

题解955 字
# 图论 # Codeforces # 树
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

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

#题目描述

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

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

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

#输入格式

第一行输入一个整数 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

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

  • 3→1→53 \rarr 1 \rarr 5，长度为 33；
  • 44，长度为 11；
  • 22，长度为 11。

#数据范围与约定

对于 100%100\% 的数据，1≤t≤1041 \leq t \leq 10^4，1≤n≤2×1051 \leq n \leq 2 \times 10^5，1≤pi≤n1 \leq p_i \leq n。

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

#思路

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

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

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

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

具体实现可以看代码。

#代码

C++
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;
}