CF963B Destruction of a Tree 题解

CF963B Destruction of a Tree 题解

  洛谷题目链接

  这里提供一个较为朴素的 DP 想法。

题意简述

  给定一棵树,节点个数不超过 \(2 \times 10^5\),每次可以删掉度数为偶数的点。问最后能不能删完;能删完给出删除方案。

思路分析

  首先可以随便选一个点作为根。

  其次,我们考虑在一棵子树的删除情况,我们令根节点为 \(u\),它的直接儿子为 \(v_1,v_2 \dots v_k\)。考虑根节点的删除情况,以及删除时需要参考什么东西。我们发现,根节点删除分为两种情况:1.它的父节点被删除了,也就是这颗子树没有(根节点的)“支上去”的那条边;2.它的父节点还没删除,我就删除根节点。此时是有“支上去”的那条边的。

  于是,我们令 \(f_{u,t} ,t \in \{0,1\}\)\(f_{u,0}\) 表示没有“支上去”的那条边的时候,是否可以删除;\(f_{u,1}\) 表示有“支上去”的那条边的时候,是否可以删除。根据定义, \(f_{u,t} \in \{0,1\}\) ,即状态表示的是“不可以”或者“可以”。

  我们考虑子树内如何合理安排删除。我们假设我们现在已经知道了所有 \(v_i,(1 \le i \le k)\)\(f_{v_i,0}\)\(f_{v_i,1}\) 结果。首先,如果存在 \(f_{v_i,0} = 0\)\(f_{v_i,1} = 0\),那么显然无论如何安排删除顺序,也不能保证删除成功。

  接下来我们分析如何安排删除顺序。我们发现,对于 \(f_{v_i,0} = 0\)\(f_{v_i,1} = 1\) 的子节点,应当先删掉它所在的那颗子树(因为要保留 \(u\)\(v_i\) 的那条边的时候才能删)。对于 \(f_{v_i,0} = 1\)\(f_{v_i,1} = 0\) 的节点,我们必须在删掉 \(u\) 之后删。对于\(f_{v_i,0} = 1\)\(f_{v_i,1} = 1\) 的节点,随便安排。

  然后我们考虑根节点如何删除。我们发现,如果删掉前面必须删的那些点后,根节点剩下的边是偶数条,那就删掉,然后 \(f_{u,0} \gets 1\) 即可。但是这里就有一个问题,假如说我们剩奇数条边的时候,我们可以再先删掉一个 \(f_{v_i,0} = 1\)\(f_{v_i,1} = 1\) 的节点来使得度数变成偶数。于是这里要再判断一下。

  奇数的时候同理,注意“支上去”的边也是连在根节点上的,所以对应的,\(f_{u,1} \gets 1\)

  具体实现的时候,我们不妨把一个点的子节点按照 \(f_{v_i,0} = 0\)\(f_{v_i,1} = 1\)的节点在前面,\(f_{v_i,0} = 1\)\(f_{v_i,1} = 1\)的节点在中间,\(f_{v_i,0} = 1\)\(f_{v_i,1} = 0\)的节点在后面,以此来排序。

  输出方案的时候,我们可以对于每个点,搜索对应状态(比如根节点是1,从\(f_{1,0}\)开始搜索),再递归下去(对于\(f_{v_i,0} = 1\)\(f_{v_i,1} = 1\)的节点,我们随便钦定一个就行)。所以一共是两遍dfs,第一遍求状态,第二遍根据状态信息推出顺序。第二遍dfs的时候,代码中的分类有所简化,如果不清楚,可以尝试先各类写一遍再简化合并。

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 2e5 + 5;

struct edge
{
	int v,next;
}e[N*2];

int head[N];
int cnt;

void adde(int u,int v)
{
	++cnt;
	e[cnt].v =v;
	e[cnt].next = head[u];
	head[u] = cnt;
}

int n;
bool f[N][2];
vector<int> output;

struct node
{
	int idx;
	bool ck0,ck1;
};

bool cmp1(const node xx,const node yy)
{
	if(xx.ck1 != yy.ck1)
		return xx.ck1 > yy.ck1;
	return xx.ck0 < yy.ck0;
}

vector<node> vec[N];
int deg[N];
int tdx[N];

bool dfs(int u,int fa)
{
	bool check = true;
	for(int i = head[u];i != 0;i = e[i].next)
	{
		int v = e[i].v;
		if(v != fa)
		{
			deg[u]++;
			dfs(v,u);
			if(f[v][0] == 0 && f[v][1] == 0)
			{
				check = false;
				break;
			}
			vec[u].push_back({v,f[v][0],f[v][1]});
		}
	}
	if(deg == 0)
	{
		f[u][1] = 0;
		f[u][0] = 1;
	}
	else
	{
		sort(vec[u].begin(),vec[u].end(),cmp1);
		tdx[u] = -1;
		for(int i = 0;i < vec[u].size();i++)
		{
			if(vec[u][i].ck1 == 1 && vec[u][i].ck0 == 0)
			{
				tdx[u] = i;
			}
			else 
			{
				break;
			}
		}
		bool mody = false;
		if(tdx[u]+1 < vec[u].size() && vec[u][tdx[u]+1].ck1 == 1 &&  vec[u][tdx[u]+1].ck1 == 0)
		{
			mody = true;
		}
		if((deg[u]-(tdx[u]+1))%2 == 0)
		{
			f[u][0] = 1;
			if(mody)
				f[u][1] = 1;
		}
		else
		{
			f[u][1] = 1;
			if(mody)
				f[u][0] = 1;
		}
	}
	return check;
}

void efs(int u,int st)
{
	int i = 0;
	for(;i <= tdx[u];i++)
	{
		efs(vec[u][i].idx,1);
	}
	if(st == 0)
	{
		if((deg[u]-(tdx[u]+1))%2 != 0)
		{
			efs(vec[u][i].idx,1);
			i++;
		}
	}
	else
	{
		if((deg[u]-(tdx[u]+1))%2 != 1)
		{
			efs(vec[u][i].idx,1);
			i++;
		}
	}
	output.push_back(u);
	for(;i < vec[u].size();i++)
	{
		efs(vec[u][i].idx,0);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		int u;
		cin >> u;
		if(u != 0)
		{
			adde(u,i);
			adde(i,u);
		}
	}
	bool res = dfs(1,0);
	if(res == 0 || f[1][0] == 0)
	{
		cout << "NO\n";
		return 0;
	}
	cout << "YES\n";
	efs(1,0);
	for(int i = 0;i < output.size();i++)
	{
		cout << output[i] << "\n";
	}
	return 0;
}

热门相关:隐婚试爱:娇妻,好甜!   上将大叔,狼来了!   上将大叔,狼来了!   网游三国之城市攻略   慕少,你老婆又重生了