专栏文章

CF2062D Balanced Tree 题解

__fairytale_
CF2062D题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miqdq0vz
此快照首次捕获于
2025/12/04 03:07
3 个月前
此快照最后确认于
2025/12/04 03:07
3 个月前
查看原文
-87，哈哈。
我们随便定一个根，然后把操作改写成子树 +1+1，或者全局 +1+1，子树 −1-1。
有一个性质是，在每个点的 aa 确定的时候，我们自底向上考虑每棵子树，对于点 uu，如果我们忽略掉全局加，那么它子树中的值都会变成 aua_u。
回到原题，一个贪心的想法是直接令 ai=lia_i=l_i。我们发现在叶子上这么做完全没有问题，问题出现在一个点小于它子树的时候，这个时候会带来一个全局加，但是全局加不优于子树加，于是记录一下儿子的 max⁡\max，取 aia_i 为尽可能接近儿子 max⁡\max 的值即可。
CPP
void Solve_(){
	int n;
	cin>>n;
	vector<int>l(n+1),r(n+1);
	rep(i,1,n)cin>>l[i]>>r[i];
	vector<vector<int>>g(n+1);
	for(int i=2,u,v;i<=n;++i){
		cin>>u>>v;
		g[u].ep(v),g[v].ep(u);
	} 
	vector<ll>f(n+1);
	vector<int>a(n+1);
	auto dfs=[&](auto &self,int u,int fa)->void{
		for(int v:g[u])if(v!=fa){
			self(self,v,u);
			ckmax(a[u],a[v]);
			f[u]+=f[v];
		}
		if(a[u]<l[u])a[u]=l[u];
		else if(a[u]>r[u])a[u]=r[u];
		for(int v:g[u])if(v!=fa)if(a[u]<a[v])f[u]+=a[v]-a[u];
	};
	dfs(dfs,1,0);
	cout<<a[1]+f[1]<<'\n';
}

评论

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

正在加载评论...