AT2304 Cleaning

题意

一个树上每个节点有一些石子，每次只能选取两个叶子节点并将路径间的所有点上的石子数量减1，问是否能将所有石子取完。

思路

设 \(f_x\) 表示从 \(x\) 节点向上的路径条数，\(s_x\) 为子节点的 \(f\) 值的和，则有：

\[a_x=\frac{s_x-f_x}{2}+f_x\\
f_x=2a_x-s_x
\]

我们只需要保证以下条件即可：

从子节点传上来的路径条数的最大值小于等于该点石头个数；
向上传的路径条数不为负且小于等于该点石头数。

也就是说，在合法条件下，我们令能在子树内匹配的路径数尽量多，然后向上传路径。

可以证明，在满足上面两个条件下，总能构造出一种合法方案使这个点合法。

其他条件：

子叶节点的 \(f_x=a_x\)；
根节点不能为子节点；
若根节点的 \(f\) 值不为0，判定为无解。

实现

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cctype>

#include<cstring>

#include<cmath>

using namespace std;

inline int read(){

	int w=0,x=0;char c=getchar();

	while(!isdigit(c))w|=c=='-',c=getchar();

	while(isdigit(c))x=x*10+(c^48),c=getchar();

	return w?-x:x;

}

namespace star

{

	const int maxn=1e5+10;

	int n,a[maxn],root;

	int ecnt,head[maxn],to[maxn<<1],nxt[maxn<<1],in[maxn],f[maxn];

	inline void addedge(int a,int b){

		to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;in[a]++;

		to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;in[b]++;

	}

	void dfs(int x,int fa){

		f[x]=in[x]==1?a[x]:(a[x]<<1);

		for(int i=head[x];i;i=nxt[i]){

			int u=to[i];

			if(u==fa)continue;

			dfs(u,x);

			f[x]-=f[u];

			if(f[u]>a[x]) puts("NO"),exit(0);

		}

		if(f[x]>a[x] or f[x]<0) puts("NO"),exit(0);

	}

	inline void work(){

		n=read();

		for(int i=1;i<=n;i++) a[i]=read();

		for(int i=1;i<n;i++) addedge(read(),read());

		if(n==2) return puts(a[1]==a[2]?"YES":"NO"),void();

		for(int i=1;i<=n;i++) if(in[i]!=1){root=i;break;}

		dfs(root,0);

		puts(f[root]?"NO":"YES");

	}

}

signed main(){

	star::work();

	return 0;

}

巴特西

AT2304 Cleaning

AT2304 Cleaning

题意

思路

实现

最新文章

热门文章