Codeforces Round #475 (Div. 2) D. Destruction of a Tree

首先达成一个共识，n为偶数，无法做到
因为n为偶数，最后奇数条边，和每次撕偶数条边不符合

n为奇数时，做dfs
首先一个除了root每个点都是奇数度的树，可以通过先序序列把这个树撕掉(这个自己脑补)
如果上述成立，那么我可以直接dfs，从离叶子最近的地方找这种树，并且把他撕掉
大概就像从叶子不断向上撕差不多
就可以了
核心就是找 除了root每个点都是奇数度的最小子树

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
#define MS(x, y) memset(x, y, sizeof(x))
#define MP(x, y) make_pair(x, y)
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 9;

vector<int> E[N];
int sz[N];
int degree[N];
int Stack[N];
int tot;
int Id[N];
void dfs(int x, int pre) {
    sz[x] = 1;
    Stack[++tot] = x;
    Id[x] = tot;
    if (pre != x)
        degree[x] ^= 1;
    int evenp = 1;
    for (int i = 0; i < E[x].size(); ++i) {
        int to = E[x][i];
        if (to == pre)
            continue;
        dfs(to, x);
        sz[x] += sz[to];
        if (sz[to]) {
            degree[x] ^= 1;
            evenp &= (sz[to] & 1);
        }
    }
    if (evenp && (degree[x] == 0)) {
        sz[x] = 0;
        for (int i = Id[x]; i <= tot; ++i) {
            printf("%d
", Stack[i]);
        }
        tot = Id[x] - 1;
    }
}
int main() {
    int n;
    while (~scanf("%d", &n)) {
        tot = 0;
        memset(degree, 0, sizeof(degree));
        for (int i = 1; i <= n; ++i)
            E[i].clear();
        int rt;
        for (int i = 1; i <= n; ++i) {
            int a;
            scanf("%d", &a);
            if (a) {
                E[i].push_back(a);
                E[a].push_back(i);
            }
        }
        if (n % 2 == 0) {
            printf("NO
");
        } else {
            printf("YES
");
            dfs(1, 1);
        }
    }
    return 0;
}
/*
5
0 1 2 1 2
5
5
0 1 2 3 3
*/