CF1987E 题解

CF1987E 题解

题意

给定一棵大小为 \(n\) 的有根树，各点各有一点权 \(a_i\)。每次操作可以选定一节点使其点权加一，求最小的操作数，使得任一节点满足其点权不大于其所有儿子的点权之和。

\(n \le 5000 ,0 \le a_i \le 10^9\)

题解

麻了，赛后十五分钟调出来，可惜为时已晚。

读懂题之后容易发现，题目最核心的地方在于当我们需要一个节点 \(+1\) 时，如果这个节点刚好等于儿子的点权和，那么就意味着需要有一个儿子节点 \(+1\) ；而这个儿子如果刚好等于其儿子的点权和，那就意味着它的儿子也有一个需要 \(+1\)，一直递归下去......直到某一节点点权严格小于其儿子的点权和，或者这个节点是叶子。

也就是说，如果一个节点需要 \(+1\) ，那么需要操作的节点就是包含其自身往下一直延伸的一条链，到叶子或者点权严格小于儿子点权和的节点为止，代价即为这条链的长度。

那么我们就可以令 \(b_v=(\sum_{u ∈ L}a_u)-a_v\) ，其中 \(L\) 为点 \(v\) 的子节点构成的集合。特别的，叶子节点的 \(b\) 为无限。

对于新定义的权值 \(b\) ，原题意就转化为：对任意节点 \(v\)，单次操作可以选定 \(v\) 子树中除自己外任一节点 \(u\) ，使\(b_v=b_v+1,b_u=b_u-1\)；操作的代价为 \(u\) 到 \(v\) 的距离。最小化使得所有节点 \(v\) 满足 \(0 \le b_v\) 的代价。

这是怎么来的呢？当我们按原题意操作了一条链时，注意到对链上除最深的节点也就是链尾之外，其他的节点权值与其儿子节点权值和之差保持不变；而链尾的这个差（也就是 \(b\) ）缩小了 \(1\)，链首父亲的 \(b\) 增加了 \(1\)。根据原题意，我们要的就是所有的节点的 \(b\) 值不小于 \(0\)。

所以对于每个 \(b < 0\) 的节点，我们只要贪心地先选深度小的且其 \(b\) 值仍为正数的后代，扣它的 \(b\) 值来填自己的，如果它的 \(b\) 值不够填那就把它的 \(b\) 值耗完再找下一个深度小的，不够再往下，反正叶子节点的 \(b\) 是正无穷，只要有后代就一定能填上，只是代价大小的问题。容易证明这样贪心能使总代价最小——把深度浅的后代自己不拿去填，留给自己的父亲填不会更优。

具体实现就是在遍历过程中对每个节点维护其后代 \(b\) 值尚可被压榨利用的点集，如果自身 \(b>0\) 则向上合并点集时将自身纳入点集（容易证明自身一定是自己父亲利用的第一选择）；反之，则优先选择自身后代贡献的点集中深度较小的来填自身的 \(b\) 值直到 \(b=0\) 。容易发现我们需要在维护过程中保持这个点集是单调的，用归并即可。推荐用 std::vector 维护点集并按降序维护，因为将自身纳入点集时我们没有 push_front() 这个函数 。

归并帮我们在合并时压掉了一个 \(\log n\) 的复杂度，但是由于树本身形状的不确定，失去了点分治中树重心那样优秀的性质，最终的时间复杂度仍然是 \(O(n^2)\)。

const ll maxn=5e3+5;
ll a[maxn],siz[maxn],dep[maxn];
ll b[maxn],ans;
ll n;
vector<ll>e[maxn];
void dfs(ll x){//预处理出 b 值
	siz[x]=1;
	b[x]=-a[x];
	for(auto v:e[x]){
		dep[v]=dep[x]+1;//标 dep 便于计算代价
		b[x]+=a[v];
		dfs(v);
		siz[x]+=siz[v];
	}
	if(siz[x]==1)b[x]=1ll<<31;//叶子的 b 值为正无穷
}
vector<ll>work(ll x){//返回的是点集
	vector<ll>lst;//自己的点集
	for(auto v:e[x]){
		vector<ll>res=work(v);
		vector<ll>tmp;
		ll l=0,r=0,len1=lst.size(),len2=res.size();
		while(l<len1||r<len2){//归并
			if(l==len1)tmp.push_back(res[r++]);
			else if(r==len2)tmp.push_back(lst[l++]);
			else if(dep[lst[l]]>dep[res[r]])tmp.push_back(lst[l++]);
			else tmp.push_back(res[r++]);
		}
		lst.swap(tmp);
	}
	if(b[x]>0)lst.push_back(x);//b>0 则放入自身
	else if(b[x]<0){
		ll p=lst.size()-1;//不用验空，b<0 其必有儿子，有儿子必有后代为叶子
		while(b[x]<0){
			ll it=lst[p];
			ll sum=min(-b[x],b[it]);//要么直接填满，要么把这个用完
			b[it]-=sum,b[x]+=sum;
			ans+=sum*(dep[it]-dep[x]);//代价
			if(b[it]==0)p--,lst.pop_back();//用完扔掉不然单调性没法保证
		}
	}
	return lst;//自身点集向上合并
}
void solve(){
	n=R;
	ans=0;//清多测
	for(ll i=1;i<=n;i++){
		a[i]=R;
		e[i].clear();//这里好一点的写法是用 tmp.swap(e[i]) 彻底释放空间
        //但由于题目保证了数据总和，抢时间就不写太麻烦了
	}
	for(ll i=2;i<=n;i++)e[R].push_back(i);
	dfs(1);
	work(1);
	we(ans);
	return ;
}

赛时还是不要放弃啊，我要是中间没有开摆这题就有时间切掉了。