Cleaning

xianghaoyu666 · 2025-09-21 17:26:10 · 个人记录

Cleaning 题解报告

洛谷

Atcoder

题意

有一棵树，每个节点的值是 A_i ，每次操作选择两个叶子结点，且它们之间的路径上的所有节点 A_i 不为零 ，将叶子结点之间的路径上的所有节点 A_i 减一，问能否让所有节点的 A_i 变成零。

分析

两个节点之间的路径 A_i 全部减一，可以用树上差分，从叶子结点向上，将两点的差分数组加一，两点 LCA 和 LCA 的父亲减一，就可以实现路径 O(1) 修改。

::::info[树上差分] 要实现路径修改，需从下往上差分

因为

红色表示路径，蓝色表示差分的前缀和传递

如果是由上至下，那就会对整个子树造成影响，不好统计

将 A_u + 1 , A_v + 1 , A_{lca(u,v)} -1 , A_{Father[lca(u,v)]} - 1 ::::

差分

那问题就转化为在一个差分后的数组上，每次选择两个叶子减一，再把它们的 LCA 和 LCA 的父亲加一， 最后叶子结点和其他节点的差分数组都等于 0 时即可 ::::info[差分代码]{open}

void dfs1(int x,int fa){  //差分预处理  
    for(auto i:g[x]){
        if(i==fa){
            continue;
        }
        a[x]-=a[i];  //先减后下传 
        dfs1(i,x);
    }
    return;
}

:::: 但枚举叶子太慢了，有没有既能做差分，又能统计叶子的呢？

DFS

从低到高 DFS ，先把自己用子树的结果变成 0 ，再往上传递以祖先为 LCA 的叶子个数

int dfs2(int x,int fa)

一定要记得是在差分树上，只用管 LCA

对于每个节点，考虑以它为 LCA 的叶子匹配个数，将 a_i 减为 0

如果 a_i > 0 就无解

if(a[x]>0){
   cout<<"NO";
   exit(0); //强制退出程序
}

接下来考虑子树

每一步，我们在不同的两个子树中同时减少一个叶子

两种情况：

• 子树中最大的路径数的大于 \lfloor \frac {sum}{2} \rfloor

容易发现，此时最多能将最大的路径与其他路径匹配，得 ans = sum - mx

• 子树中最大的路径数的小于等于 \lfloor \frac {sum}{2} \rfloor

这时没有浪费的路径，故 ans = \lfloor \frac {sum}{2} \rfloor

实现为

::::info[计算路径]{open}

int s=0-a[x]; //需要多少条路径以 x 为 LCA 来将 Ax 填成 0 
if(mx>ans/2){ //最大值比 ans/2 大，有浪费 
  if(ans-mx<s){
    cout<<"NO";
    exit(0);
  }
}else{ //最大值比 ans/2 小，无浪费 
  if(ans/2<s){
    cout<<"NO";
    exit(0);
  }
}

::::

最后，需要减去 2 \times (-a[x]) 个叶子结点（填自己）

记住！！！

这是在差分数组上更新路径， A_{fa[x]} 也要加 s

所以子节点的 DFS 会改变 A_x 的值，一定要先传递儿子再对自己判断，不然不符合下面可以帮助上面的贪心策略

::::warning[代码]{open}

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
int a[100010];
int u,v;
vector<int>g[100010];
bool f=0;
int d[100010];
void dfs1(int x,int fa){  //???? 
    for(auto i:g[x]){
        if(i==fa){
            continue;
        }
        a[x]-=a[i]; 
        dfs1(i,x);
    }
    return;
}
int dfs2(int x,int fa){
    int mx=-0x3f3f3f3f3f3f3f3f,ans=0;
    for(auto i:g[x]){
        if(i==fa){
            continue;
        }
        int now=dfs2(i,x);
        mx=max(mx,now); 
        ans+=now;
    }
    if(g[x].size()==1 && fa!=0){
        return a[x];
    }
    if(a[x]>0){
        cout<<"NO";
        exit(0);
    }
    int s=0-a[x]; //需要多少条路径以 x 为 LCA 来将 Ax 填成 0 
    if(mx>ans/2){ //最大值比 ans/2 大，有浪费 
        if(ans-mx<s){
            cout<<"NO";
            exit(0);
        }
    }else{ //最大值比 ans/2 小，无浪费 
        if(ans/2<s){
            cout<<"NO";
            exit(0);
        }
    }
    ans-=2*s;
    a[fa]+=s;
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        d[u]++;
        d[v]++;
    }
    for(int i=1;i<=n;i++){
        if(d[i]>1){
            d[i]++;
            dfs1(i,0);
            int c=dfs2(i,0);
            if(c!=0){
                cout<<"NO";
            }else{
                cout<<"YES";
            }
            return 0;
        }
    }
    return 0;
}

::::

散花？

为什么呢？

1

我们的做法都基于每个节点有两个及以上的儿子，那万一只有一个儿子呢？

简易分析可得：

• 当 A_x = 0 时，把所有叶子传递即可
• 当 A_x \neq 0 时，无解，输出 "NO"

if(g[x].size()==2 && fa!=0){
 if(a[x]!=0){
   cout<<"NO";
   exit(0);
 }else{
   return ans;
 }
}

2

我们选择一个度数大于 1 的节点作为根，可 2 \leq N \leq 10^5 ，当 N = 2 时，所有点的度数都为 1 ，没有根，需特判

if(n==2){
 if(a[1]==a[2]){
   cout<<"YES"<<endl;
 }else{
   cout<<"NO"<<endl;
 }
 return 0;
}

AC Code

::::success[AC]

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int n;
int a[100010];
int u,v;
vector<int>g[100010];
bool f=0;
int d[100010];
void dfs1(int x,int fa){  //???? 
    for(auto i:g[x]){
        if(i==fa){
            continue;
        }
        a[x]-=a[i]; 
        dfs1(i,x);
    }
    return;
}
int dfs2(int x,int fa){
    int mx=-0x3f3f3f3f3f3f3f3f,ans=0;
    for(auto i:g[x]){
        if(i==fa){
            continue;
        }
        int now=dfs2(i,x);
        mx=max(mx,now); 
        ans+=now;
    }
    if(g[x].size()==1 && fa!=0){
        return a[x];
    }
    if(a[x]>0){
        cout<<"NO";
        exit(0);
    }
    if(g[x].size()==2 && fa!=0){
        if(a[x]!=0){
            cout<<"NO";
            exit(0);
        }else{
            return ans;
        }
    }
    int s=0-a[x];
    if(mx>ans/2){
        if(ans-mx<s){
            cout<<"NO";
            exit(0);
        }
    }else{
        if(ans/2<s){
            cout<<"NO";
            exit(0);
        }
    }
    ans-=2*s;
    a[fa]+=s;
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        d[u]++;
        d[v]++;
    }
    if(n==2){
        if(a[1]==a[2]){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(d[i]>1){
            d[i]++;
            dfs1(i,0);
            int c=dfs2(i,0);
            if(c!=0){
                cout<<"NO";
            }else{
                cout<<"YES";
            }
            return 0;
        }
    }
    return 0;
}

::::

后记

附上评测记录