The Fox and the Complete Tree Traversal 题解

plank_black · 2023-06-01 21:03:49 · 题解

审核大大幸苦了~~

思路

构造题当然要先模拟几组小样例看一下规律。

玩了几组后我们发现其实合法的情况挺少的，比如下面这一组就是合法的方案：

下面这种就不行：

大家可以再自己随便造一些数据试试（也不能太随便），最后可以发现其实只有第一个图这种情况符合条件，也就是只有当能在这颗树中找到一条链，使得删去这条链剩下的所有子树都只有一个点时才有解。

要证明其实也不难，我们参考下图进行证明，箭头表示所指方向还有若干点，且有一种方案可以将这些点跳完。

假定我们从左边跳来，当我们跳到了这个子图上时，有第一个点两种情况，在 A 点和在 B 点上，进行一个分类讨论。

初始在 A 点上。

若刚开始不跳到支链上，那么回来时就必须先跳到 B 上再跳完支链再返回，但实际上想要跳完支链就必须经过一个先 E 再 D 的过程或者是先 D 再 E 的过程，但无论哪种都是无法跳到 A 的左边，所以这个方案不行。
第一次跳到 D 点，然后向 C 点右跳，回来时先到 B 点，再把 E 点和下面的点跳完，这时候 B,D,E 已经把路堵死了，所以这个方案不行。
第一次就把支链跳完，必然先 D 再 E，然后再跳到 B 上，再向右跳，可以发现回来的路已经堵死了，所以这个方案不行。

初始在 B 上。

若刚开始不跳到支链上，那么回来时就必须由 C 点到 D 点上，然后跳完 E 下面的点之后再回到 E 就发现跳不动了，所以这个方案不行。
若刚开始跳一个 D，再到 C，会发现回来的路已经堵死了，所以这个方案不行。
若刚开始完支链，那么必然会先到先跳到 E 点，然后再回到 D 点，再到 C 点，然后你发现回来的路又堵死了，所以这个方案也不行。

有点啰嗦的证明就这样写完了（

然后我们就只需要判断这颗树中是否有一条链使得去掉它之后剩下的子树都是单个节点。

这里还有一个结论，就是我们要找的这条链就是当前树的最长链。如果这条链与最长链不一样，那么用最长链替换这条链肯定会更优，这在当前链与最长链有重合与没有重合的情况下都是可证明的。证明比较简单这里就省去了。

现在就已知了主链，以及挂在主链上的只能是一个个单独的点，然后就只用构造一种方案输出就行。方案就是从最长链一个端点开始向另一个端点走，偶数步就输出当前链上的这个点，奇数步就输出所有连在这个点上的非主链上的点。然后倒着输出一遍差不多的操作。

于是我们就只需要愉快地 DFS 就可以 A 掉这道题了（

代码

为了让代码思路更清晰，我把代码细分成了 7 个 DFS（

#include<iostream>
#include<cstring>
using namespace std;

const int N = 2e5 + 10;
int n, p1, p2, Max;
int head[N], to[N * 2], Next[N * 2], Index;
int size[N], dep[N];
bool in[N], flag = true;

void add(int a, int b);
void dfs1(int u, int p);
void dfs2(int u, int p);
void dfs3(int u, int p);
void dfs4(int u, int p);
void dfs5(int u, int p);
void output1(int u, int p);
void output2(int u, int p);

int main( ) {
    memset(head, -1, sizeof head); 

    cin >> n;
    for(int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b), add(b, a);
    }

    dfs1(1, 0);

    Max = 0;
    dfs2(p1, 0);

    in[p2] = true;
    dfs3(p1, 0);

    memset(dep, 0, sizeof dep);
    dfs4(p1, 0);

    dfs5(p1, 0);

    if(flag) {
        cout << "Yes" << endl;
        output1(p1, 0);
        output2(p1, 0);
    }
    else cout << "No" << endl;
    return 0;
}

void add(int a, int b) {
    to[Index] = b;
    Next[Index] = head[a], head[a] = Index++;
}

void dfs1(int u, int p) { // dfs1 和 dfs2 都是用来找最长链的
    dep[u] = dep[p] + 1;
    if(Max < dep[u]) {
        Max = dep[u];
        p1 = u;
    }

    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p) dfs1(j, u);
    }
}

void dfs2(int u, int p) {
    dep[u] = dep[p] + 1;
    if(Max < dep[u]) {
        Max = dep[u];
        p2 = u;
    }

    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p) dfs2(j, u);
    }
}

void dfs3(int u, int p) { // 记录主链
    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p) {
            dfs3(j, u);
            in[u] |= in[j];
        }
    }
}

void dfs4(int u, int p) { // 初始化 size 和深度
    size[u] = 1;
    dep[u] = dep[p] + 1;
    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p) {
            dfs4(j, u);
            size[u] += size[p];
        }
    }
}

void dfs5(int u, int p) { // 判断是不是挂在主链上的都是单个点，用flag记录
    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p) {
            dfs5(j, u);
            if(size[j] >= 2 && !in[j]) flag = false;
        }
    }
}

void output1(int u, int p) { //正着输
    if(dep[u] % 2) {
        for(int t = head[u]; ~t; t = Next[t]) 
            if(!in[to[t]]) cout << to[t] << ' ';
    } else cout << u << ' ';

    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p && in[j]) output1(j, u);
    }
}

void output2(int u, int p) { // 倒着输
    for(int i = head[u]; ~i; i = Next[i]) {
        int j = to[i];
        if(j != p && in[j]) output2(j, u);
    }

    if(dep[u] % 2 == 0) {
        for(int t = head[u]; ~t; t = Next[t]) 
            if(!in[to[t]]) cout << to[t] << ' ';
    } else cout << u << ' ';
}