题解 AT2304 【Cleaning】

· · 题解

戳我＝￣ω￣＝

这个里面的花，我们在所有的叶子节点i中放a_i个小精灵。每一次所有小精灵都会往父亲飞，当一群小精灵聚集在x这个节点时，从不同儿子节点飞上来的小精灵可以选择组成一对“好朋友”，并且以后不再往父亲走。接着小精灵们会开始捡石头，一对“好朋友”只会捡走一个石头，单身的小精灵每人捡走一个石头，石头必须被捡完，所以组成多少对朋友就是固定的。然后没有找到朋友的小精灵会继续往父亲节点飞。问是否所有小精灵都能找到朋友并且所有石头都要被捡完。

那么会前文已说，从每个节点继续往上飞的小精灵数是固定的，所以每个节点处组成朋友的小精灵对数也是固定的，重点在求出最多可以组成多少对朋友，判断能不能达成石头恰好被捡完这个目标。

那么这个找朋友的过程怎么进行呢？我们让从同一个儿子节点飞上来的小精灵暂时站在一艘船上，由于只有不同船上的小精灵可以组队，所以有精灵的船越多越有利。所以我们每次选择两艘小精灵数最多的船，让它们上面各一个小精灵组成一对，然后她们两个下船，以此类推。

于是我们发现最多能组的队数只有两种情况，一种是有一艘船上的小精灵特别多，多到别的船都空了这艘船上还有很多小精灵单身。一种是我们这么操作着操作着所有船上的小精灵数越来越多接近，最后几乎所有的小精灵都有了朋友，但是如果总精灵数是奇数，那必然有一个小精灵找不到朋友。

最多组的队数与想要石头恰好被捡完应该组的队数比较即可判断。

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
typedef long long LL;
const int N=100005;
int n,tot,h[N],ne[N<<1],to[N<<1],du[N];
LL a[N],f[N];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x,int las) {
    if(du[x]==1) {f[x]=a[x];return;}
    LL orzabs=0,p,mx=0;
    for(RI i=h[x];i;i=ne[i]) {
        if(to[i]==las) continue;
        dfs(to[i],x),f[x]+=f[to[i]],mx=max(mx,f[to[i]]);
    }
    if(mx>f[x]-mx) p=f[x]-mx;
    else p=f[x]/2;
    if(f[x]<a[x]) {puts("NO");exit(0);}
    if(f[x]-a[x]>p) {puts("NO");exit(0);}
    f[x]-=(f[x]-a[x])*2LL;
}
int main()
{
    int x,y;
    n=read();
    for(RI i=1;i<=n;++i) a[i]=read();
    if(n==2) {
        if(a[1]==a[2]) puts("YES");
        else puts("NO");
        return 0;
    }
    for(RI i=1;i<n;++i)
        x=read(),y=read(),add(x,y),add(y,x),++du[x],++du[y];
    for(RI i=1;i<=n;++i) if(du[i]>1) {
        dfs(i,0);
        if(f[i]) puts("NO");
        else puts("YES");
        return 0;
    }
    return 0;
}