command_block 的博客

command_block 的博客

[??记录]CF963B Destruction of a Tree

posted on 2021-11-17 21:30:48 | under 记录 |

题意 : 给出一棵 $n$ 个节点的无向无根树。

每次可以删除度数为偶数的某个节点,以及相连的所有边。

构造一种删完整棵树的方案,或指出无解。

$n\leq 2\times 10^5$ ,时限 $\texttt{1s}$。


注意到所有叶子节点在父节点被删除之前都不可以删除。

我们考虑儿子只有叶节点的点,它的删除要晚于所有儿子。

若度数为偶数,则它的删除要晚于父亲,反之则要早于父亲。

对于一般情况,统计有几个儿子必须要在自己之后删,加上一条父边,根据奇偶性看自己要在父亲 先/后 删。

对于根,如果有奇数个需要后删的儿子,则无解,偶数个则有解。

拓扑排序构造方案,复杂度 $O(n)$ 。

#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define MaxN 200500
using namespace std;
vector<int> g[MaxN],g2[MaxN];
int d[MaxN],f[MaxN];
void dfs(int u,int fa)
{
  for (int i=0;i<g[u].size();i++){
    int v=g[u][i];dfs(v,u);
    f[u]^=f[v];
  }
  f[u]^=1;
  if (fa){
    if (f[u]){g2[fa].pb(u);d[u]++;}
    else {g2[u].pb(fa);d[fa]++;}
  }
}
int n,q[MaxN];
int main()
{
  scanf("%d",&n);
  int rt;
  for (int i=1,fa;i<=n;i++){
    scanf("%d",&fa);
    if (fa)g[fa].pb(i);
    else rt=i;
  }
  dfs(rt,0);
  if (!f[rt]){puts("NO");return 0;}
  puts("YES");
  int tl=1,tr=0;
  for (int i=1;i<=n;i++)if (!d[i])q[++tr]=i;
  while(tl<=tr){
    int u=q[tl++];
    for (int i=0;i<g2[u].size();i++)
      if (!--d[g2[u][i]])q[++tr]=g2[u][i];
  }for (int i=1;i<=n;i++)printf("%d\n",q[i]);
  return 0;
}