[NOIP2024] 树的遍历

GitHub 跳转原题关系图返回列表

把边遍历看成线图 DFS 树计数，先算单根方案，再用树形 DP 统计关键边对的重复贡献。

OJ: luogu

题目 ID: P11363

难度:提高+/省选-

标签:树形结构动态规划组合计数

日期: 2026-06-22 19:19

题意

给定一棵 n 个点的树。现在把原树中的每条边看成一个新结点，两条边有公共端点就认为它们相邻。

从一条关键边出发，按 DFS 的方式遍历所有边。每次第一次走到一条新边时，就在“上一条边”和“这条新边”对应的新结点之间连边。最终会得到一棵由 n-1 个新结点组成的新树。

问从任意关键边出发，可能得到多少种不同的新树。

思路

先看一个小数据暴力：在线图上直接枚举 DFS 的每一步选择，把得到的新树放进集合去重。

cpp

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// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;

int case_id, T;
int n, k;
pair<int, int> edge_list[MAXN];
int key_edge[MAXN];
bool adjacent_edge[MAXN][MAXN];
set<vector<pair<int, int> > > all_trees;

void dfs_line_graph(int root, int current, int visited_mask, vector<int> parent_stack, vector<pair<int, int> > tree_edges) {
    bool moved = false;
    for (int i = 1; i < n; i++) {
        if ((visited_mask & (1 << (i - 1))) || !adjacent_edge[current][i]) {
            continue;
        }
        moved = true;
        vector<pair<int, int> > next_edges = tree_edges;
        int a = current, b = i;
        if (a > b) {
            swap(a, b);
        }
        next_edges.push_back(make_pair(a, b));

        vector<int> next_stack = parent_stack;
        next_stack.push_back(current);
        dfs_line_graph(root, i, visited_mask | (1 << (i - 1)), next_stack, next_edges);
    }

    if (moved) {
        return;
    }

    if (current == root) {
        if (visited_mask == (1 << (n - 1)) - 1) {
            sort(tree_edges.begin(), tree_edges.end());
            all_trees.insert(tree_edges);
        }
    } else {
        int parent = parent_stack.back();
        parent_stack.pop_back();
        dfs_line_graph(root, parent, visited_mask, parent_stack, tree_edges);
    }
}

bool share_endpoint(pair<int, int> a, pair<int, int> b) {
    return a.first == b.first || a.first == b.second || a.second == b.first || a.second == b.second;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> case_id >> T;
    while (T--) {
        cin >> n >> k;
        for (int i = 1; i < n; i++) {
            cin >> edge_list[i].first >> edge_list[i].second;
        }
        for (int i = 1; i <= k; i++) {
            cin >> key_edge[i];
        }

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < n; j++) {
                adjacent_edge[i][j] = (i != j && share_endpoint(edge_list[i], edge_list[j]));
            }
        }

        all_trees.clear();
        for (int i = 1; i <= k; i++) {
            vector<int> empty_stack;
            vector<pair<int, int> > empty_edges;
            int root = key_edge[i];
            dfs_line_graph(root, root, 1 << (root - 1), empty_stack, empty_edges);
        }

        cout << all_trees.size() << '\n';
    }

    return 0;
}

暴力会枚举大量 DFS 顺序，无法处理 n=10^5。

先考虑只有一条关键边作为起点。原树中某个点 u 连接着 deg(u) 条边。DFS 从其中一条边来到这个点附近后，剩下 deg(u)-1 条边可以按任意顺序被展开，所以这个点贡献：

text

1(deg(u)-1)!

所有点相互独立，因此单个起点的方案数是：

text

1base = prod (deg(u)-1)!

如果有 k 条关键边，先看成有 k * base 种。但同一棵新树可能由两条不同关键边作为起点得到，需要减去重复。

两条关键边会重复，取决于它们在原树中之间的路径。路径经过点 u 时，路径两侧的两条边必须在 u 的局部 DFS 顺序中紧挨着。相比任意顺序，这会让局部方案数除以：

text

1deg(u)-1

于是定义点权：

text

1
2w(u) = 1 / (deg(u)-1)    deg(u)>1
w(u) = 1                deg(u)=1

一对关键边的重复权值，就是它们之间路径上点权的乘积。设所有关键边对的重复权值和为 pair_bad，答案为：

text

1base * (k - pair_bad)

现在问题变成：求所有关键边对之间的路径点权乘积之和。

把原树任意定根，做树形 DP：

g[u]：从 u 的子树中某条关键边走到 u 的路径权值和；
f[u]：u 子树内已经统计出的关键边对重复权值和。

合并 u 的多个孩子时，不同孩子子树中的关键边对会在 u 处相遇，贡献要乘上 w(u)。如果 u 的父边本身是关键边，它也可以和子树中的关键边配对。

用这个 DP 求出 pair_bad = f[root]，再代入公式即可。

代码

cpp

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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const long long MOD = 1000000007LL;

struct Edge {
    int to;
    int id;
};

int case_id, T;
int n, k;
int degree_cnt[MAXN];
bool is_key[MAXN];
long long fact[MAXN], inv_num[MAXN];
long long weight_node[MAXN];
long long f[MAXN], g[MAXN];
int parent_node[MAXN], parent_edge[MAXN];
vector<Edge> tree[MAXN];
vector<int> order_list;

long long power_mod(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b > 0) {
        if (b & 1LL) {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1LL;
    }
    return res;
}

void prepare_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i - 1] * i % MOD;
    }
    for (int i = 1; i < MAXN; i++) {
        inv_num[i] = power_mod(i, MOD - 2);
    }
}

void clear_case() {
    for (int i = 1; i <= n; i++) {
        tree[i].clear();
        degree_cnt[i] = 0;
        f[i] = g[i] = 0;
        parent_node[i] = parent_edge[i] = 0;
    }
    for (int i = 1; i < n; i++) {
        is_key[i] = false;
    }
    order_list.clear();
}

void build_rooted_tree() {
    order_list.clear();
    order_list.push_back(1);
    parent_node[1] = 0;
    parent_edge[1] = 0;

    for (int i = 0; i < (int)order_list.size(); i++) {
        int u = order_list[i];
        for (int j = 0; j < (int)tree[u].size(); j++) {
            int v = tree[u][j].to;
            int id = tree[u][j].id;
            if (v == parent_node[u]) {
                continue;
            }
            parent_node[v] = u;
            parent_edge[v] = id;
            order_list.push_back(v);
        }
    }
}

long long solve_one() {
    long long base = 1;
    for (int i = 1; i <= n; i++) {
        base = base * fact[degree_cnt[i] - 1] % MOD;
        if (degree_cnt[i] <= 1) {
            weight_node[i] = 1;
        } else {
            weight_node[i] = inv_num[degree_cnt[i] - 1];
        }
    }

    build_rooted_tree();

    for (int idx = (int)order_list.size() - 1; idx >= 0; idx--) {
        int u = order_list[idx];
        long long sum_g = 0;
        long long sum_square = 0;
        f[u] = 0;

        for (int j = 0; j < (int)tree[u].size(); j++) {
            int v = tree[u][j].to;
            if (parent_node[v] != u) {
                continue;
            }
            f[u] += f[v];
            if (f[u] >= MOD) {
                f[u] -= MOD;
            }
            sum_g += g[v];
            if (sum_g >= MOD) {
                sum_g -= MOD;
            }
            sum_square = (sum_square + g[v] * g[v]) % MOD;
        }

        long long pair_sum = (sum_g * sum_g % MOD - sum_square + MOD) % MOD;
        pair_sum = pair_sum * inv_num[2] % MOD * weight_node[u] % MOD;
        f[u] = (f[u] + pair_sum) % MOD;

        if (is_key[parent_edge[u]]) {
            f[u] = (f[u] + sum_g * weight_node[u]) % MOD;
            g[u] = 1;
        } else {
            g[u] = sum_g * weight_node[u] % MOD;
        }
    }

    long long choose_one = k % MOD;
    long long multiplier = (choose_one - f[1] + MOD) % MOD;
    return base * multiplier % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    prepare_factorials();

    cin >> case_id >> T;
    while (T--) {
        cin >> n >> k;
        clear_case();

        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            tree[u].push_back((Edge){v, i});
            tree[v].push_back((Edge){u, i});
            degree_cnt[u]++;
            degree_cnt[v]++;
        }

        for (int i = 1; i <= k; i++) {
            int id;
            cin >> id;
            is_key[id] = true;
        }

        cout << solve_one() << '\n';
    }

    return 0;
}

复杂度

每组数据只需要遍历原树常数次，时间复杂度为 $O(n)$ 。

空间复杂度为 $O(n)$ 。

总结

本题的关键是把“边的 DFS”理解成原树线图上的 DFS 树计数。

单个起点的数量是每个原树点局部展开顺序的乘积。多个关键边起点的重复，则由关键边对之间的路径决定，用树形 DP 统计所有路径权值和即可。

P11363 [NOIP2024] 树的遍历

题目描述

小 Q 是一个算法竞赛初学者，正在学习图论知识中的树的遍历。一棵由 $n$ 个结点， $n - 1$ 条边构成的树，初始时所有结点都未被标记，它的遍历过程如下：

选择一个结点 $s$ 作为遍历起始结点，并把该结点打上标记。
假设当前访问的结点为 $u$ ，寻找任意一个与 $u$ 相邻且未标记的结点 $v$ ，将 $v$ 作为新的当前访问结点并打上标记。之后再次进入第 $2$ 步。
假设在第 $2$ 步中，与 $u$ 相邻的结点都已被标记，如果 $u = s$ 则遍历过程结束，否则将 $u$ 设为遍历 $u$ 之前的上一个结点并再进入第 $2$ 步。

例如在下面的树中，一种可能的遍历过程如下：

选取 $1$ 作为遍历起始结点，并把 $1$ 打上标记；
$2$ 与 $1$ 相邻且未标记，将 $2$ 设为当前访问结点，并把 $2$ 打上标记。
$2$ 与 $3$ 相邻且未标记，将 $3$ 设为当前访问结点，并把 $3$ 打上标记。
$3$ 所有相邻的结点都被标记，将当前访问结点设为遍历结点 $3$ 之前的结点 $2$ 。
$2$ 与 $4$ 相邻且未标记，将 $4$ 设为当前访问结点，并把 $4$ 打上标记。
$4$ 所有相邻的结点都被标记，将当前访问结点设为遍历结点 $4$ 之前的结点 $2$ 。
$2$ 所有相邻的结点都被标记，将当前访问结点设为遍历结点 $2$ 之前的结点 $1$ 。
$1$ 所有相邻的结点都被标记，且 $1$ 是遍历起始结点，故遍历结束。

作为一个奇思妙想的学生，小 Q 在学习完上述知识后不满足于以结点为基础的遍历方式，于是开始研究以边为基础的遍历方式。定义两条边相邻，当且仅当它们有一个公共的结点。初始时，所有的边都未被标记。这种以边为基础的遍历过程如下：

选择一条边 $b$ 作为遍历起始边，并把该边打上标记。
假设当前访问边为 $e$ ，寻找任意一条与 $e$ 相邻且未标记的边 $f$ ，将 $f$ 作为新的当前访问边并打上标记。之后再次进入第 $2$ 步。
假设在第 $2$ 步中，与 $e$ 相邻的边都已被标记，如果 $e = b$ 则遍历过程结束，否则将 $e$ 设为遍历 $e$ 之前的上一条边并再进入第 $2$ 步。

例如在上面的树中，一种可能的遍历过程如下（定义 $\{u, v\}$ 表示连接结点 $u$ 和 $v$ 的边）：

选取 $\{1, 2\}$ 作为遍历起始边，并把 $\{1, 2\}$ 打上标记；
$\{1, 2\}$ 与 $\{2, 3\}$ 相邻且未标记，将 $\{2, 3\}$ 设为当前访问边，并把 $\{2, 3\}$ 打上标记。
$\{2, 3\}$ 与 $\{2, 4\}$ 相邻且未标记，将 $\{2, 4\}$ 设为当前访问边，并把 $\{2, 4\}$ 打上标记。
$\{2, 4\}$ 所有相邻的边都被标记，将当前访问边设为遍历 $\{2, 4\}$ 之前的边 $\{2, 3\}$ 。
$\{2, 3\}$ 所有相邻的边都被标记，将当前访问边设为遍历 $\{2, 3\}$ 之前的边 $\{1, 2\}$ 。
$\{1, 2\}$ 所有相邻的边都被标记，且 $\{1, 2\}$ 是遍历起始边，故遍历结束。

小 Q 惊奇的发现，在这个新的树的遍历过程中，如果将每条边看作一个新的结点，将步骤 $2$ 中的所有新结点 $e$ 和 $f$ 连接一条新边，就会生成一棵由 $n-1$ 个新结点和 $n-2$ 条新边连接成的新树。例如上述遍历过程得到的新树如下（新的结点和新边都用红色表示）：

现在小 Q 在 $n - 1$ 条边中选择了 $k$ 条关键边。小 Q 想知道，以任意一条关键边作为起始遍历边，通过上述遍历过程能够生成多少种不同的新树。这里两棵树被认为是不同的，当且仅当至少存在某一对新的结点，它们仅在其中一棵树中连有新边。

由于结果可能很大，你只需要输出其对 $10^9+7$ 取模的结果即可。

输入格式

本题有多组测试数据。

输入的第一行包含两个整数 $c, T$ ，表示测试点的编号和测试数据的组数。在样例中， $c$ 表示该样例与测试点 $c$ 的数据范围相同。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含两个整数 $n, k$ ，表示树的结点数以及小 Q 选择的关键边的数量。
接下来 $n - 1$ 行，第 $i$ 行包含两个整数 $u_i, v_i$ ，表示树上编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$ 。
接下来一行包含 $k$ 个整数 $e_1, e_2, \dots, e_k$ ，表示小 Q 选择的关键边的编号。保证关键边的编号互不相同。

输出格式

对于每组测试数据输出一行，包含一个整数，表示结果对 $10^9 + 7$ 取模的结果。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

【样例 1 解释】

两种可能的新树如下：

新结点 $\{1, 2\}$ 和新结点 $\{2, 3\}$ 连新边，新结点 $\{2, 3\}$ 和新结点 $\{2, 4\}$ 连新边。
新结点 $\{1, 2\}$ 和新结点 $\{2, 4\}$ 连新边，新结点 $\{2, 4\}$ 和新结点 $\{2, 3\}$ 连新边。

【样例 2 解释】

三种可能的新树如下：

新结点 $\{1, 2\}$ 和 $\{1, 3\}$ ， $\{1, 2\}$ 和 $\{2, 4\}$ ， $\{2, 4\}$ 和 $\{2, 5\}$ 之间分别连新边。该新树可以选择 $\{1, 2\}$ 作为起始遍历边得到。
新结点 $\{1, 2\}$ 和 $\{1, 3\}$ ， $\{1, 2\}$ 和 $\{2, 5\}$ ， $\{2, 5\}$ 和 $\{2, 4\}$ 之间分别连新边。该新树可以选择 $\{1, 2\}$ 或 $\{2, 4\}$ 作为起始遍历边得到。
新结点 $\{1, 2\}$ 和 $\{1, 3\}$ ， $\{1, 2\}$ 和 $\{2, 4\}$ ， $\{1, 2\}$ 和 $\{2, 5\}$ 之间分别连新边。该新树可以选择 $\{2, 4\}$ 作为起始遍历边得到。

【样例 3】

见附件的 traverse/traverse3.in 与 traverse/traverse3.ans。

该组样例满足 $c = 4$ 。

【样例 4】

见附件的 traverse/traverse4.in 与 traverse/traverse4.ans。

该组样例满足 $c = 7$ 。

【样例 5】

见附件的 traverse/traverse5.in 与 traverse/traverse5.ans。

该组样例满足 $c = 11$ 。

【样例 6】

见附件的 traverse/traverse6.in 与 traverse/traverse6.ans。

该组样例满足 $c = 13$ 。

【样例 7】

见附件的 traverse/traverse7.in 与 traverse/traverse7.ans。

该组样例满足 $c = 15$ 。

【样例 8】

见附件的 traverse/traverse8.in 与 traverse/traverse8.ans。

该组样例满足 $c = 16$ 。

【样例 9】

见附件的 traverse/traverse9.in 与 traverse/traverse9.ans。

该组样例满足 $c = 18$ 。

【样例 10】

见附件的 traverse/traverse10.in 与 traverse/traverse10.ans。

该组样例满足 $c = 19$ 。

【样例 11】

见附件的 traverse/traverse11.in 与 traverse/traverse11.ans。

该组样例满足 $c = 22$ 。

【样例 12】

见附件的 traverse/traverse12.in 与 traverse/traverse12.ans。

该组样例满足 $c = 24$ 。

【数据范围】

对于所有的测试数据，保证：

$1 \leq T \leq 10$ ；
$2 \leq n \leq 10^5$ ；
$1 \leq k < n$ ；
对于任意的 $i(1 \leq i \leq n - 1)$ ，都有 $1 \leq u_i, v_i \leq n$ ，且构成一颗合法的树。
对于任意的 $i(1 \leq i \leq k)$ ，都有 $1 \leq e_i < n$ ，且两两不同。

::cute-table{tuack}

测试点编号	$n$	$k$	特殊性质
$1\sim 3$	$\leq 5$	$\leq 1$	无
$4\sim 6$	$\leq 10^5$	^	^
$7\sim 10$	^	$\leq 2$	^
$11,12$	$\leq 500$	$\leq 8$	^
$13,14$	$\leq 10^2$	$<n$	^
$15$	$\leq 500$	^	^
$16,17$	$\leq 10^5$	$\leq 500$	^
$18$	^	$<n$	A
$19\sim 21$	^	^	B
$22,23$	$\leq 2\times 10^4$	^	无
$24,25$	$\leq 10^5$	^	^

特殊性质 A：对于任意的 $i(1 \leq i \leq n - 1)$ ，都有 $u_i = i, v_i = i + 1$ 。
特殊性质 B：对于任意的 $i(1 \leq i \leq n - 1)$ ，都有 $u_i = 1, v_i = i + 1$ 。

【提示】

数据输入的规模可能较大，请选手注意输入读取方式的效率。

[NOIP2024] 树的遍历

目录

题意

思路

代码

复杂度

总结