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，判定为无解。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #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;
}
|
