专栏文章

Cleaning

xxianghaoyu666
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minty2e3
此快照首次捕获于
2025/12/02 08:18
3 个月前
此快照最后确认于
2025/12/02 08:18
3 个月前
查看原文

Cleaning 题解报告

洛谷
Atcoder

题意

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

分析

两个节点之间的路径 AiA_i 全部减一，可以用树上差分，从叶子结点向上，将两点的差分数组加一，两点 LCA 和 LCA 的父亲减一，就可以实现路径 O(1)O(1) 修改。
树上差分
要实现路径修改，需从下往上差分
因为
图 红色表示路径，蓝色表示差分的前缀和传递
如果是由上至下，那就会对整个子树造成影响，不好统计
将 Au+1 A_u + 1 , Av+1A_v + 1 , Alca(u,v)−1A_{lca(u,v)} -1 , AFather[lca(u,v)]−1A_{Father[lca(u,v)]} - 1

差分

那问题就转化为在一个差分后的数组上，每次选择两个叶子减一，再把它们的 LCA 和 LCA 的父亲加一， 最后叶子结点和其他节点的差分数组都等于 0 时即可
差分代码CPP
void dfs1(int x,int fa){  //差分预处理  
	for(auto i:g[x]){
		if(i==fa){
			continue;
		}
		a[x]-=a[i];  //先减后下传 
		dfs1(i,x);
	}
	return;
}
但枚举叶子太慢了，有没有既能做差分，又能统计叶子的呢？

DFS

从低到高 DFSDFS，先把自己用子树的结果变成 0 ，再往上传递以祖先为 LCA 的叶子个数
CPP
int dfs2(int x,int fa)
一定要记得是在差分树上，只用管 LCA
对于每个节点，考虑以它为 LCA 的叶子匹配个数，将 aia_i 减为 0
如果 ai>0a_i > 0 就无解
CPP
if(a[x]>0){
   cout<<"NO";
   exit(0); //强制退出程序
}
接下来考虑子树
每一步，我们在不同的两个子树中同时减少一个叶子
两种情况：
  • 子树中最大的路径数的大于 ⌊sum2⌋\lfloor \frac {sum}{2} \rfloor
容易发现，此时最多能将最大的路径与其他路径匹配，得 ans=sum−mxans = sum - mx
  • 子树中最大的路径数的小于等于 ⌊sum2⌋\lfloor \frac {sum}{2} \rfloor
这时没有浪费的路径，故 ans=⌊sum2⌋ans = \lfloor \frac {sum}{2} \rfloor
实现为
计算路径CPP
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×(−a[x])2 \times (-a[x]) 个叶子结点（填自己）
记住！！！
这是在差分数组上更新路径，Afa[x]A_{fa[x]} 也要加 ss
所以子节点的 DFSDFS 会改变 AxA_x 的值，一定要先传递儿子再对自己判断，不然不符合下面可以帮助上面的贪心策略
代码CPP
#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;
}

散花？

JUDGE
为什么呢？

1

我们的做法都基于每个节点有两个及以上的儿子，那万一只有一个儿子呢？
简易分析可得：
  • 当 Ax=0A_x = 0 时，把所有叶子传递即可
  • 当 Ax≠0A_x \neq 0 时，无解，输出 "NO"
CPP
if(g[x].size()==2 && fa!=0){
 if(a[x]!=0){
   cout<<"NO";
   exit(0);
 }else{
   return ans;
 }
}

2

我们选择一个度数大于 1 的节点作为根，可 2≤N≤1052 \leq N \leq 10^5 ，当 N=2N = 2 时，所有点的度数都为 1 ，没有根，需特判
CPP
if(n==2){
 if(a[1]==a[2]){
   cout<<"YES"<<endl;
 }else{
   cout<<"NO"<<endl;
 }
 return 0;
}

AC Code

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

后记

附上评测记录
LUDGE2

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...