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

题意：给你一棵树，只能删度数为偶数的点，问你能不能将整个图删完，如果能输入删除的顺序。

思路：对于一棵树来说，如果里面的点的个数是偶数个则肯定不可能，偶数个点有奇数条边，而你每次删只能删偶数条边。

那么我们对于每个父亲儿子来说，如果儿子的子树的大小为奇数，那么肯定先删父亲，反之先删儿子，建立关系图，跑一遍拓扑序就好啦。

 #include<bits/stdc++.h>

 #define LL long long

 #define fi first

 #define se second

 #define mk make_pair

 #define pii pair<int,int>

 #define ull unsigned long long

 using namespace std;

 const int N=1e6+;

 const int M=+;

 const int inf=0x3f3f3f3f;

 const LL INF=0x3f3f3f3f3f3f3f3f;

 const int mod=1e9 + ;

 vector<int> edge[N], e[N], ans;

 int n, cnt[N], deg[N];

 int vis[N];

 void dfs(int u ,int pre) {

     cnt[u] = ;

     for(int v : edge[u]) {

         if(v == pre) continue;

         dfs(v, u);

         cnt[u] += cnt[v];

     }

 }

 bool dfs2(int u) {

     vis[u] = -;

     for(int v : e[u]) {

         if(vis[v] == -)

             return false;

         if(!vis[v] && !dfs2(v))

             return false;

     }

     vis[u] = ;

     ans.push_back(u);

     return true;

 }

 void dfs3(int u, int pre) {

     for(int v : edge[u]) {

         if(v == pre) continue;

         if(cnt[v] % ) {

             e[u].push_back(v);

             deg[v]++;

         } else {

             e[v].push_back(u);

             deg[u]++;

         }

         dfs3(v, u);

     }

 }

 int main() {

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         int fa; scanf("%d", &fa);

         if(fa) {

             edge[fa].push_back(i);

             edge[i].push_back(fa);

         }

     }

     if(n %  == ) {

         puts("NO");

         return ;

     }

     dfs(, );

     dfs3(, );

     for(int i = ; i <= n; i++) {

         if(vis[i]) continue;

         if(!dfs2(i)) {

             puts("NO");

             return ;

         }

     }

     puts("YES");

     for(int i = ans.size() - ; i >= ; i--)

         printf("%d\n", ans[i]);

     return ;

 }

 /*

 */

巴特西

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

最新文章

热门文章