[??记录]AT2304 [AGC010C] Cleaning

· · 个人记录

题意 ： 一棵树，第 i 个节点上有 a_i 个石头。

每次可以选择两个不同的叶节点（度数为 1 的节点），将两点间路径上的所有节点都取走一个石头，如果有某个点上没石头这个操作就不能进行。

判定能不能取完所有石头。

------------ 先任找一个不是叶子的点为根。（若 $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

当 u 点为根时，额外要求 f_u=0。

若满足上述条件，不难归纳证明可以构造出合法方案。

复杂度 O(n)。

#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;
}