[??记录]AT2304 [AGC010C] Cleaning
command_block
2021-04-28 07:11:57
**题意** ： 一棵树，第 $i$ 个节点上有 $a_i$ 个石头。
每次可以选择两个不同的叶节点（度数为 $1$ 的节点），将两点间路径上的所有节点都取走一个石头，如果有某个点上没石头这个操作就不能进行。
判定能不能取完所有石头。
$n\leq 10^5$ ，时限$\texttt{2s}$。
------------
先任找一个不是叶子的点为根。（若 $n=2$ 则都是叶子，特判）
记 $f_u$ 表示方案中穿过 $u$ 的路径数目。对于叶节点，有 $f_u=a_u$。
对于非叶节点，记 $s_u=\sum\limits_{u\rightarrow v}f_v$ ，即从儿子延伸上来的路径条数。
这些路径可以选择两两合并，也可以继续延伸。可以列出方程 ：
$$a_u=\dfrac{s_u-f_u}{2}+f_u=\dfrac{s_u+f_u}{2}$$
$$f_u=2a_u-s_u$$
根据这个方程，可以用一次 $\rm dfs$ 求出所有的 $f,s$。
然后考虑如何判定，一个显然的条件是 $0\leq f_u,s_u$。
此外，$f_u,s_u$ 各有上界。记 $c_u$ 为子树内叶节点的权值和，则 ：
- $f_u\leq c_u$
- $\dfrac{s_u-f_u}{2}\leq s_u-\max\limits_{u\rightarrow v}f_v)$
这个套路和 [[DS记录]P4338 [ZJOI2018]历史](https://www.luogu.com.cn/blog/command-block/ds-ji-lu-p4338-zjoi2018-li-shi) 一致。
当 $u$ 点为根时，额外要求 $f_u=0$。
若满足上述条件，不难归纳证明可以构造出合法方案。
复杂度 $O(n)$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 100500
using namespace std;
vector<int> g[MaxN];
ll a[MaxN],f[MaxN],c[MaxN];
bool fl;
void dfs(int u,int fa)
{
if (g[u].size()==1){
c[u]=f[u]=a[u];
return ;
}
ll s=0,mx=0;
for (int i=0,v;i<g[u].size();i++)
if ((v=g[u][i])!=fa){
dfs(v,u);
s+=f[v];
c[u]+=c[v];
mx=max(mx,c[v]);
}
f[u]=2*a[u]-s;
if (f[u]<0||s<0||f[u]>c[u]||(s-f[u])/2>min(c[u]/2,c[u]-mx))fl=0;
if (!fa&&f[u]>0)fl=0;
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%lld",&a[i]);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}
if (n==2){
puts(a[1]==a[2] ? "YES" : "NO");
return 0;
}
int rt=0;
for (int i=1;i<=n;i++)
if (g[i].size()>1)rt=i;
fl=1;dfs(rt,0);
puts(fl ? "YES" : "NO");
return 0;
}
```