[??记录]CF963B Destruction of a Tree
command_block
2021-11-17 21:30:48
**题意** ： 给出一棵 $n$ 个节点的无向无根树。
每次可以删除度数为偶数的某个节点，以及相连的所有边。
构造一种删完整棵树的方案，或指出无解。
$n\leq 2\times 10^5$ ，时限 $\texttt{1s}$。
------------
注意到所有叶子节点在父节点被删除之前都不可以删除。
我们考虑儿子只有叶节点的点，它的删除要晚于所有儿子。
若度数为偶数，则它的删除要晚于父亲，反之则要早于父亲。
对于一般情况，统计有几个儿子必须要在自己之后删，加上一条父边，根据奇偶性看自己要在父亲 先/后 删。
对于根，如果有奇数个需要后删的儿子，则无解，偶数个则有解。
拓扑排序构造方案，复杂度 $O(n)$ 。
```cpp
#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;
}
```