2021 ICPC Southeastern Europe Regional Contest K Amazing Tree

题目描述

https://codeforces.com/gym/103438/problem/K

简要题意：给定义一棵 $n$ 个点的树，可以从任意一个点开始 $dfs$，求后根遍历的最小可能字典序

$n < 2\times 10^5$

Solution

容易发现，后根遍历的第一个点一定是最小的叶子 $v$，那么接下来我们只能返回到 $v$ 的父亲 $u$，对于 $u$，我们有两种抉择，一种是认为 $u$ 是我们所选定的根，那么我们会将 $u$ 的除 $v$ 以外的子树按照最小叶子排序依次 $dfs$，最终将 $u$ 加入答案；或者认为 $u$ 还有父亲，那么我们会将 $u$ 的除 $v$ 以外的子树按照最小叶子排序，不妨假设有 $k$ 个子树，先依次 $dfs$ 前 $k - 1$ 个，然后将 $u$ 加入答案，然后 $dfs$ 最后一个子树

至于实现，我们以最小的叶子为根建树，这样方便得到每个子树的最小叶子，同时在 $dfs$ 的时候，我们记录现在是在向上还是向下

#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 200010
#define INF 1000000000
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int w[maxn], du[maxn];
void pre(int u, int fa) {
    bool isleaf = true; w[u] = INF;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        isleaf = false; pre(v, u); w[u] = min(w[u], w[v]); 
    } if (isleaf) w[u] = u; 
}

vector<int> ans;
void dfs(int u, int fa, int f) {
    vector<pair<int, int>> vec;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        vec.emplace_back(w[v], v); 
    } sort(vec.begin(), vec.end());
    if (!vec.size()) return ans.push_back(u);
    if (!f) {
        for (int i = 0; i < vec.size(); ++i) dfs(vec[i].second, u, 0);
        ans.push_back(u); 
    } else {
        for (int i = 0; i < vec.size() - 1; ++i) dfs(vec[i].second, u, 0);
        if (u > vec.back().first) dfs(vec.back().second, u, 0), ans.push_back(u);
        else ans.push_back(u), dfs(vec.back().second, u, 1); 
    }
}

void work() {
    cin >> n; fill(head + 1, head + n + 1, -1); c1 = 0; ans.clear(); 
    for (int i = 1; i <= n; ++i) du[i] = 0; 
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
        ++du[x]; ++du[y];
    } int p = 0; for (int i = n; i; --i) if (du[i] == 1) p = i;
    pre(p, 0); dfs(p, 0, 1);
    for (auto u : ans) cout << u << " "; cout << "\n";
}

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

    int T; cin >> T;
    while (T--) work(); 
    return 0;
}