cf#963B Destruction of a Tree(贪心

题目

http://codeforces.com/problemset/problem/963/B

题目大意

一棵树，每次消除度数为偶数的叶子节点以及他所有的边，问这个数能否被消除完（度数为0也是偶数哦）。能消除玩需要输出消除的顺序。

算法思路

将数dfs排序，每次先消除度数为偶数的dfs序大的节点。若先消除根节点，其叶子节点要是无法消除就没有办法了。
（贪心消除最靠近叶子的节点。因为如果最靠近叶子的偶数度节点晚于父节点消除，则父节点消除后此节点度数变为奇数，且其所有子节点度数都为奇数，就再也消除不了了。）

代码

#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;//记录其父亲节点
 st.push(u);//会按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;

}