[Codeforces] 475D Destruction of a Tree

題目連結：http://codeforces.com/contest/964/problem/D
　　觀察到偶數個點的時候，由於共有奇數個邊，但每次都只能拔掉偶數個邊，所以一定NO，而奇數則一定可以，從葉子做上來，假設拔掉了一個點，考慮其其中一個子樹，若其根的deg為奇數，則這點拔掉前為偶數，所以會先拔掉這個點才對；若為偶數，那就從這個點往下拔，由於不會出現第一種case，所以一定會拔光，因此奇數一定YES。
　　謹記遇到樹的時候要從子樹開始做之類的。

#include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 9;
int n;
vector<int> G[N];
int deg[N];
bool done[N];
void split(int u,int f)
{
    cout << u << '\n'; 
    done[u] = 1;
    for(auto i:G[u]) deg[i] ^= 1;
    for(auto i:G[u]) if(i != f && !deg[i] && !done[i]) split(i,u);
}
void dfs(int u,int f)
{
    for(auto i:G[u]) if(i != f) dfs(i,u);
    if(!deg[u]) split(u,f);
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        int a; cin >> a; if(a == 0) continue;
        G[i].push_back(a); G[a].push_back(i);
        deg[i] ^= 1; deg[a] ^= 1;
    }
    if(n %2 == 0) cout << "NO\n";
    else cout << "YES\n", dfs(1,1);
}