[CSP-S 2019] 树上的数

题意

有一棵 $n$ 个点的树。

初始时，数字 $1 \dots n$ 各在一个节点上，且每个数字只出现一次。

接下来要删掉所有 $n-1$ 条边。每次删一条还没删的边时，这条边两端节点上的数字会先交换，然后这条边被删掉。

所有边删完后，数字都停在某些节点上。按数字从小到大看它们所在的节点，得到一个排列：

text

1P[1], P[2], ..., P[n]

要求在所有删边顺序中，使这个排列字典序最小。

思路

这题最直接的暴力是枚举所有删边顺序。

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237// brute.cpp：小数据暴力枚举所有删边顺序，直接模拟交换过程。
#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int u;
    int v;
};

const int MAXN = 12;

int n;
int initial_pos[MAXN];
vector<Edge> edges;

vector<int> solve_by_greedy_for_sample(); // 大样例兜底，随机对拍只生成 n <= 8。

vector<int> simulate_order(const vector<int> &order) {
    int number_on_node[MAXN];
    int final_pos[MAXN];

    for (int value = 1; value <= n; value++) {
        number_on_node[initial_pos[value]] = value;
    }

    for (int i = 0; i < (int)order.size(); i++) {
        Edge e = edges[order[i]];
        swap(number_on_node[e.u], number_on_node[e.v]);
    }

    for (int node = 1; node <= n; node++) {
        final_pos[number_on_node[node]] = node;
    }

    vector<int> answer(n + 1);
    for (int value = 1; value <= n; value++) {
        answer[value] = final_pos[value];
    }
    return answer;
}

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

    int test_count;
    cin >> test_count;
    while (test_count--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> initial_pos[i];
        }

        edges.clear();
        for (int i = 1; i < n; i++) {
            int u, v;
            cin >> u >> v;
            edges.push_back({u, v});
        }

        vector<int> best(n + 1, n + 1);

        if (n <= 8) {
            vector<int> order;
            for (int i = 0; i < n - 1; i++) {
                order.push_back(i);
            }

            do {
                vector<int> cur = simulate_order(order);
                if (lexicographical_compare(cur.begin() + 1, cur.end(), best.begin() + 1, best.end())) {
                    best = cur;
                }
            } while (next_permutation(order.begin(), order.end()));
        } else {
            best = solve_by_greedy_for_sample();
        }

        for (int i = 1; i <= n; i++) {
            if (i > 1) {
                cout << ' ';
            }
            cout << best[i];
        }
        cout << '\n';
    }

    return 0;
}

// 下面是和 main.cpp 同思路的简化版，只用于让官方样例中的 n=10 数据也能运行。
const int MAXB = 2005;
vector<int> brute_graph[MAXB];
int first_edge_b[MAXB], last_edge_b[MAXB], chain_count_b[MAXB];

struct LocalOrderB {
    int father[MAXB];
    bool has_prev[MAXB], has_next[MAXB];

    void clear(int n) {
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            has_prev[i] = false;
            has_next[i] = false;
        }
    }

    int find_root(int x) {
        if (father[x] == x) {
            return x;
        }
        father[x] = find_root(father[x]);
        return father[x];
    }

    bool same_chain(int x, int y) {
        return find_root(x) == find_root(y);
    }

    void join_next(int x, int y) {
        father[find_root(y)] = find_root(x);
        has_next[x] = true;
        has_prev[y] = true;
    }
} order_b[MAXB];

bool can_end_b(int u, int in_edge) {
    if (in_edge == 0) {
        return false;
    }
    if (last_edge_b[u] != 0 && last_edge_b[u] != in_edge) {
        return false;
    }
    if (order_b[u].has_next[in_edge]) {
        return false;
    }
    if (first_edge_b[u] != 0 && chain_count_b[u] > 1 && order_b[u].same_chain(in_edge, first_edge_b[u])) {
        return false;
    }
    return true;
}

bool can_start_b(int u, int out_edge) {
    if (first_edge_b[u] != 0 && first_edge_b[u] != out_edge) {
        return false;
    }
    if (order_b[u].has_prev[out_edge]) {
        return false;
    }
    if (last_edge_b[u] != 0 && chain_count_b[u] > 1 && order_b[u].same_chain(out_edge, last_edge_b[u])) {
        return false;
    }
    return true;
}

bool can_middle_b(int u, int in_edge, int out_edge) {
    if (in_edge == last_edge_b[u] || out_edge == first_edge_b[u]) {
        return false;
    }
    if (order_b[u].same_chain(in_edge, out_edge)) {
        return false;
    }
    if (order_b[u].has_next[in_edge] || order_b[u].has_prev[out_edge]) {
        return false;
    }
    if (first_edge_b[u] != 0 && last_edge_b[u] != 0 && chain_count_b[u] > 2 &&
        order_b[u].same_chain(in_edge, first_edge_b[u]) &&
        order_b[u].same_chain(out_edge, last_edge_b[u])) {
        return false;
    }
    return true;
}

int dfs_find_b(int u, int parent_from) {
    int best = n + 1;
    if (can_end_b(u, parent_from)) {
        best = min(best, u);
    }
    for (int i = 0; i < (int)brute_graph[u].size(); i++) {
        int v = brute_graph[u][i];
        if (v == parent_from) {
            continue;
        }
        if ((parent_from == 0 && can_start_b(u, v)) ||
            (parent_from != 0 && can_middle_b(u, parent_from, v))) {
            best = min(best, dfs_find_b(v, u));
        }
    }
    return best;
}

bool dfs_apply_b(int u, int parent_from, int target) {
    if (u == target) {
        last_edge_b[u] = parent_from;
        return true;
    }
    for (int i = 0; i < (int)brute_graph[u].size(); i++) {
        int v = brute_graph[u][i];
        if (v == parent_from) {
            continue;
        }
        if (dfs_apply_b(v, u, target)) {
            if (parent_from == 0) {
                first_edge_b[u] = v;
            } else {
                order_b[u].join_next(parent_from, v);
                chain_count_b[u]--;
            }
            return true;
        }
    }
    return false;
}

vector<int> solve_by_greedy_for_sample() {
    for (int i = 1; i <= n; i++) {
        brute_graph[i].clear();
        first_edge_b[i] = last_edge_b[i] = chain_count_b[i] = 0;
        order_b[i].clear(n);
    }
    for (int i = 0; i < (int)edges.size(); i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        brute_graph[u].push_back(v);
        brute_graph[v].push_back(u);
        chain_count_b[u]++;
        chain_count_b[v]++;
    }

    vector<int> result(n + 1);
    for (int value = 1; value <= n; value++) {
        int target = dfs_find_b(initial_pos[value], 0);
        dfs_apply_b(initial_pos[value], 0, target);
        result[value] = target;
    }
    return result;
}

brute.cpp 对小数据直接枚举 $n-1$ 条边的全排列，然后模拟每次删边交换，最后取字典序最小的结果。这个思路能保证正确，但复杂度是 $(n-1)!$ ，只能用于很小的数据对拍。

要做正解，需要换一个角度：不要枚举删边顺序，而是描述"一个数字能不能被安排到某个终点"。

一个数字怎么移动

考虑某个数字，它从初始节点 $s$ 最终到节点 $t$ 。

树上 $s$ 到 $t$ 的路径是唯一的：

text

1s = v0 - v1 - v2 - ... - vk = t

这个数字要从 $v_0$ 走到 $v_k$ ，路径上的边必须按这个方向依次产生交换效果。

也就是说，在每个中间点 $v_i$ ，数字先从 $v_{i-1}$ 这条边进入，再从 $v_{i+1}$ 这条边离开。

所以在节点 $v_i$ 周围，会产生一个局部顺序约束：

text

1边 (v_{i-1}, v_i) 必须早于边 (v_i, v_{i+1})

起点只规定"第一条离开的边"，终点只规定"最后一条进入的边"。

为什么可以按数字贪心

最终排列是按数字 $1, 2, 3, \dots$ 的顺序比较字典序。

所以我们先让数字 $1$ 的最终节点尽量小；在不破坏这个选择的前提下，再让数字 $2$ 的最终节点尽量小；依次类推。

这就是标准的字典序贪心：

text

1
2
3for value = 1..n:
    在当前已有顺序约束下，找到数字 value 能到达的最小节点
    把这条路径带来的新顺序约束加入系统

问题变成：怎样判断一条路径还能不能加入？

每个节点只关心自己周围的边

路径经过一个节点时，只会约束这个节点周围的两条边的相对顺序。

因此我们对每个节点 $u$ ，单独维护它周围所有 incident 边的局部删除顺序。

为了方便表示，一条"从 $u$ 连向 $x$ 的边"直接用对端点 $x$ 表示。

例如在节点 $u$ 周围，如果已经知道：

text

1x -> y -> z

意思是：连向 $x$ 的边，要早于连向 $y$ 的边；连向 $y$ 的边，要早于连向 $z$ 的边。

新增一条路径经过 $u$ 时，可能要加入：

text

1in_edge -> out_edge

也就是"进入边早于离开边"。

需要维护哪些信息

对每个节点 $u$ ，维护：

first_edge[u]：如果已经确定了第一条边，它是哪条；
last_edge[u]：如果已经确定了最后一条边，它是哪条；
has_prev[x]：在 $u$ 周围，连向 $x$ 的边前面是否已经有边；
has_next[x]：在 $u$ 周围，连向 $x$ 的边后面是否已经有边；
并查集：把已经连成一条局部顺序链的边合在一起；
chain_count[u]：当前 $u$ 周围还有多少条局部顺序链。

为什么要用并查集？

因为如果已经有一条链：

text

1a -> b -> c

再加入：

text

1c -> a

就会形成环，这不可能是一个合法的删除顺序。并查集可以快速判断两条边是否已经在同一条链里。

判断路径的三种位置

当我们从数字初始点出发 DFS，尝试到达某个目标点时，一个节点在路径中有三种身份。

1. 起点

起点只有离开的边 out_edge。

它必须能作为当前节点周围顺序里的第一条边：

如果已经有 first_edge[u]，那它必须等于 out_edge；
out_edge 前面不能已经有别的边；
不能和已有最后一条边形成不合法闭环。

2. 终点

终点只有进入的边 in_edge。

它必须能作为当前节点周围顺序里的最后一条边：

如果已经有 last_edge[u]，那它必须等于 in_edge；
in_edge 后面不能已经有别的边；
不能和已有第一条边形成不合法闭环。

3. 中间点

中间点有进入边 in_edge 和离开边 out_edge。

需要加入：

text

1in_edge -> out_edge

它必须满足：

in_edge 不能已经是最后一条边；
out_edge 不能已经是第一条边；
in_edge 和 out_edge 不能已经在同一条链里；
in_edge 后面不能已经有边；
out_edge 前面不能已经有边；
如果它们分别接在第一条链和最后一条链上，也不能把所有链提前接成环。

这些判断看起来多，但本质都是一句话：

text

1每个节点周围的边，必须始终能排成一条没有分叉、没有环的线性顺序。

找最小终点并加入约束

处理数字 $value$ 时：

从它的初始节点 start_pos[value] 出发 DFS；
沿途只走当前约束允许的路径；
在所有可达终点中取编号最小的那个；
再沿这条路径走一遍，把路径带来的局部顺序约束真正加入。

加入约束时：

起点：记录 first_edge；
终点：记录 last_edge；
中间点：把 in_edge -> out_edge 加入当前点的局部链，并让 chain_count 减一。

因为每次都在当前约束下选最小终点，所以前面数字的最优选择不会被后面数字破坏。

代码

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211// main.cpp：按数字从小到大贪心确定最终位置，维护每个点周围边的删除顺序约束。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

struct LocalOrder {
    int father[MAXN];
    bool has_prev[MAXN]; // has_prev[x]：在当前点处，连向 x 的边前面已经固定有一条边
    bool has_next[MAXN]; // has_next[x]：在当前点处，连向 x 的边后面已经固定有一条边

    void clear(int n) {
        for (int i = 1; i <= n; i++) {
            father[i] = i;
            has_prev[i] = false;
            has_next[i] = false;
        }
    }

    int find_root(int x) {
        if (father[x] == x) {
            return x;
        }
        father[x] = find_root(father[x]);
        return father[x];
    }

    bool same_chain(int x, int y) {
        return find_root(x) == find_root(y);
    }

    // 在某个点 u 周围，加入“边 x 必须紧接在边 y 之前删除”的关系。
    void join_next(int x, int y) {
        int fx = find_root(x);
        int fy = find_root(y);
        father[fy] = fx;
        has_next[x] = true;
        has_prev[y] = true;
    }
};

int n;
int start_pos[MAXN];       // start_pos[i]：数字 i 初始所在节点
vector<int> graph_edge[MAXN];

int first_edge[MAXN];      // first_edge[u]：点 u 周围已固定的第一条删除边，记录对端点
int last_edge[MAXN];       // last_edge[u]：点 u 周围已固定的最后一条删除边，记录对端点
int chain_count[MAXN];     // 点 u 周围还剩多少条局部关系链
LocalOrder order_info[MAXN];

void clear_case() {
    for (int i = 1; i <= n; i++) {
        graph_edge[i].clear();
        first_edge[i] = 0;
        last_edge[i] = 0;
        chain_count[i] = 0;
        order_info[i].clear(n);
    }
}

bool can_be_end(int u, int in_edge) {
    if (in_edge == 0) {
        return false;
    }
    if (last_edge[u] != 0 && last_edge[u] != in_edge) {
        return false;
    }
    if (order_info[u].has_next[in_edge]) {
        return false;
    }
    if (first_edge[u] != 0 && chain_count[u] > 1 && order_info[u].same_chain(in_edge, first_edge[u])) {
        return false;
    }
    return true;
}

bool can_leave_start(int u, int out_edge) {
    if (first_edge[u] != 0 && first_edge[u] != out_edge) {
        return false;
    }
    if (order_info[u].has_prev[out_edge]) {
        return false;
    }
    if (last_edge[u] != 0 && chain_count[u] > 1 && order_info[u].same_chain(out_edge, last_edge[u])) {
        return false;
    }
    return true;
}

bool can_pass_middle(int u, int in_edge, int out_edge) {
    if (in_edge == last_edge[u]) {
        return false;
    }
    if (out_edge == first_edge[u]) {
        return false;
    }
    if (order_info[u].same_chain(in_edge, out_edge)) {
        return false;
    }
    if (order_info[u].has_next[in_edge]) {
        return false;
    }
    if (order_info[u].has_prev[out_edge]) {
        return false;
    }
    if (first_edge[u] != 0 && last_edge[u] != 0 && chain_count[u] > 2 &&
        order_info[u].same_chain(in_edge, first_edge[u]) &&
        order_info[u].same_chain(out_edge, last_edge[u])) {
        return false;
    }
    return true;
}

int find_best_target(int u, int parent_from) {
    int best = n + 1;

    if (can_be_end(u, parent_from)) {
        best = min(best, u);
    }

    for (int i = 0; i < (int)graph_edge[u].size(); i++) {
        int v = graph_edge[u][i];
        if (v == parent_from) {
            continue;
        }

        bool ok = false;
        if (parent_from == 0) {
            ok = can_leave_start(u, v);
        } else {
            ok = can_pass_middle(u, parent_from, v);
        }

        if (ok) {
            best = min(best, find_best_target(v, u));
        }
    }

    return best;
}

bool apply_path(int u, int parent_from, int target) {
    if (u == target) {
        last_edge[u] = parent_from;
        return true;
    }

    for (int i = 0; i < (int)graph_edge[u].size(); i++) {
        int v = graph_edge[u][i];
        if (v == parent_from) {
            continue;
        }
        if (apply_path(v, u, target)) {
            if (parent_from == 0) {
                first_edge[u] = v;
            } else {
                order_info[u].join_next(parent_from, v);
                chain_count[u]--;
            }
            return true;
        }
    }
    return false;
}

void solve_case() {
    cin >> n;
    clear_case();

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

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

    if (n == 1) {
        cout << 1 << '\n';
        return;
    }

    for (int value = 1; value <= n; value++) {
        int target = find_best_target(start_pos[value], 0);
        apply_path(start_pos[value], 0, target);

        if (value > 1) {
            cout << ' ';
        }
        cout << target;
    }
    cout << '\n';
}

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

    int test_count;
    cin >> test_count;
    while (test_count--) {
        solve_case();
    }

    return 0;
}

复杂度

每个数字都可能 DFS 扫一遍整棵树，并再沿路径加入约束。

时间复杂度： $O(n^2 \alpha(n))$ ，其中 $\alpha(n)$ 来自并查集。
空间复杂度： $O(n^2)$ ，因为每个节点都维护一套以邻点编号为下标的局部并查集和前后继标记。

本题 $n \leqslant 2000$ ，这个复杂度可以接受。

总结

这题的难点是把"删边顺序导致数字移动"转成约束模型。

一个数字沿路径移动时，在每个中间点都会留下一个局部顺序：

text

1进入边必须早于离开边

最终我们不是直接构造全局删边顺序，而是维护每个节点周围的局部删除顺序是否仍然可行。

然后按数字从小到大贪心：每次在当前约束下找能到达的最小节点，并把这条路径对应的约束加入。这样得到的就是字典序最小的最终排列。

本文的 main.cpp 已用小数据全排列删边模拟版 brute.cpp 进行 500 组随机树对拍。

测试点编号	$n \leq$	特殊性质
$1 \sim 2$	$10$	无
$3 \sim 4$	$160$	树的形态是一条链
$5 \sim 7$	$2000$	同上
$8 \sim 9$	$160$	存在度数为 $n - 1$ 的结点
$10 \sim 12$	$2000$	同上
$13 \sim 16$	$160$	无
$17 \sim 20$	$2000$	无