題目
http://codeforces.com/problemset/problem/963/B
題目大意
一棵樹(shù)哀九，每次消除度數(shù)為偶數(shù)的葉子節(jié)點(diǎn)以及他所有的邊剿配，問(wèn)這個(gè)數(shù)能否被消除完（度數(shù)為0也是偶數(shù)哦）。能消除玩需要輸出消除的順序勾栗。
算法思路
將數(shù)dfs排序惨篱，每次先消除度數(shù)為偶數(shù)的dfs序大的節(jié)點(diǎn)。若先消除根節(jié)點(diǎn)围俘，其葉子節(jié)點(diǎn)要是無(wú)法消除就沒(méi)有辦法了砸讳。
（貪心消除最靠近葉子的節(jié)點(diǎn)。因?yàn)槿绻羁拷~子的偶數(shù)度節(jié)點(diǎn)晚于父節(jié)點(diǎn)消除界牡，則父節(jié)點(diǎn)消除后此節(jié)點(diǎn)度數(shù)變?yōu)槠鏀?shù)簿寂，且其所有子節(jié)點(diǎn)度數(shù)都為奇數(shù)，就再也消除不了了宿亡。）
代碼
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+10;
vector<int>vec[maxn];
vector<int>ans;
stack<int>st;
int pa[maxn];
int deg[maxn];
int vis[maxn];
void dfs(int u,int pre){
pa[u]=pre;//記錄其父親節(jié)點(diǎn)
st.push(u);//會(huì)按dfs序逆序彈出常遂，這么做挺巧妙的…
for(int i=0;i<vec[u].size();i++){
int t=vec[u][i];
if(t==pre) continue;
dfs(t,u);
}
//ed[u]=tot;
}
void dfs2(int u){
vis[u]=1;
ans.push_back(u);
for(int i=0;i<vec[u].size();i++){
int t=vec[u][i];
deg[t]--;
if(t==pa[u]||vis[t]) continue;
if(deg[t]%2==0) dfs2(t);
}
}
int main(){
int n;
while(cin>>n){
for(int i=0;i<=n;i++)
vec[i].clear();
ans.clear();
while(!st.empty())
st.pop();
memset(deg,0,sizeof(deg));
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++){
int t;
cin>>t;
if(t) {
vec[i].push_back(t);
vec[t].push_back(i);
deg[t]++;
deg[i]++;}
}
dfs(1,-1);
while(!st.empty()){
int t=st.top();
st.pop();
if(deg[t]%2==0){
dfs2(t);
}
}
if(ans.size()==n){
cout<<"YES"<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i]<<endl;
}
else cout<<"NO"<<endl;
}
return 0;
}
