题解：CF2062D Balanced Tree

感觉 D 远大于 E1，卡了好久才做出来 qwq。

先考虑怎么根据区间给点赋初值更优，由于每次子树内加相当于是两个值不同的块合并的过程，合并是必定的，所以我们应当使每次加尽可能地少加一些不必要的点。因此每个叶子节点应当取最小值，记

a_v

为

v

这个点的值，对于一个点

u

，定义

k=\max_{v\in son(u)} a_v

，则

a_u

的取值为：

a_u=\begin{cases}\max(k,l_u),r_u\ge k \\ r_u,r_u<k\end{cases}

现在考虑将所有点的值变成一样的过程，应该是自底向上变成一样的。对于

u

为

v

的父亲，如果有

a_u\ge a_v

，那么可以通过一直加

v

的子树变成相同的。否则就应当把

v

作为根，将

u

的子树一直加，直到

a_u=a_v

。

现在考虑怎么维护这样的过程，加的过程相当于是将除了某一个子树整体加，最后统计单点的值，可以用 dfn 序加差分维护。

官方题解比我赛时写的更简单，因为最后每个点都是一样的值，所以只需要关注根节点的值，那么就变成当

a_v>a_u

的时候，将根节点加上

a_v-a_u

了。

代码很丑，但还是放着：

CPP

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
const int maxn=2e5+20;
#define ll long long
ll t,n,val[maxn],b[maxn],cf[maxn],dfn[maxn],tot,siz[maxn],ans,f[maxn],rev[maxn];
vector<ll> e[maxn];
struct range{
	ll l,r;
}a[maxn];
void dfs(int u,int fa){
	ll flag=0,mx=0;
	dfn[u]=++tot,siz[u]=1,f[u]=fa,rev[tot]=u;
	for(int v:e[u]){
		if(v==fa) continue;
		flag=1,dfs(v,u);
		mx=max(mx,val[v]),siz[u]+=siz[v];
	}
	if(!flag) val[u]=a[u].l;
	else{
		if(mx<=a[u].r) val[u]=max(mx,a[u].l);
		else val[u]=a[u].r;
	}
}
inline void solve(){
	n=read(),tot=ans=0;
	for(int i=0;i<=n;i++) e[i].clear(),b[i]=cf[i]=0;
	int u,v;
	for(int i=1;i<=n;i++) a[i]={read(),read()};
	for(int i=1;i<n;i++) u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
	dfs(1,0);
	for(int i=1;i<=n;i++) if(f[i]&&val[i]>val[f[i]]) b[i]=val[i]-val[f[i]];
	for(int i=1;i<=n;i++) cf[0]+=b[i],cf[dfn[i]]-=b[i],cf[dfn[i]+siz[i]]+=b[i];
	for(int i=1;i<=n;i++) cf[i]+=cf[i-1],ans=max(ans,cf[i]+val[rev[i]]);
	printf("%lld\n",ans);
}
int main(){
	t=read();
	while(t--) solve();
	return 0;
}

题解：CF2062D Balanced Tree

文章操作

相关推荐

评论

题解：CF2062D Balanced Tree