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):

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

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

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

具体实现可以看代码。

代码

#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;
}