题目

树上每个节点都有自己的需要权值，\(0\) 号点为根与源点，每次从 \(0\) 号点发 \(d\) 的权值，一个点接到权值之后会查看自己的儿子：如果有儿子还没有被满足，那么就会将权值平分给没有被满足的儿子。否则如果自己没被满足，就给自己留下权值，如果自己已经满足了，就把多余的权值返还给父亲。

询问分别使 \(i=1...n\) 中每个点被满足时从 \(0\) 号点发送的最小权值

数据范围

\(n \leq 3\times 10^5\)

题解

正着考虑很奇怪，因为同时有许许多多分数的权值在上下游走，那么考虑倒着推回去。

设当前需要满足的点为 \(u\) ，需求为 \(a_u\) ，那么可以发现与 \(u\) 同属于一个父亲的每个点 \(v\) ，在 \(u\) 被满足的时候都获得了 \(min(a_v,a_u)\) 的权值，那么我们就可以倒推出点 \(u\) 父亲获得了多少权值，递归下去推出从 \(0\) 出发了多少权值。

现在可以计算答案了，那么考虑如何快速的从 \(u\) 跳到 \(0\) ，设点 \(x\) 当前答案为 \(ans\) ，那么计算同一层的答案就是 \(\sum \min(ans,siz_u)\) ，不难发现如果 \(ans \geq \forall siz_u\) ，那么就是加上 \(\sum siz_u\) ，否则发现 \(ans\) 一定翻倍，而 \(ans\) 最多翻 \(log\) 倍，那么只需要每次知道往上跳的时候什么时候 \(ans\) 翻倍，中间的用倍增快速跳过就好了。

考虑维护出来一个倍增数组 \(f_{u,i}\) 表示从 \(u\) 点往上跳 \(2^i\) 步且不翻倍，当前答案必须 \(\geq f_{u,i}\) ，那么再维护出来 \(s_{u,i}\) 表示从点 \(u\) 往上跳 \(2^i\) 步且不翻倍答案增加多少，则转移为 \(f_{u,i}=\max (f_{u,i-1},f_{g_{u,i-1},i-1}-s_{u,i-1})\)

PS：这道题写的时候不小心把一个地方实现错了。。写多次在树上遍历一个点所有儿子还是要谨慎。。不然还真不好发现这种问题

const int N=6e5+5;
int n,fu[N],a[N],deep[N],g[N][19];
ll f[N][19],maxx[N],mixx[N];
ll s[N][19];
ll siz[N];
vi v[N],vv[N],sa[N];
double st,ed;
void dfs(int u){
	siz[u]=a[u];deep[u]=deep[fu[u]]+1;g[u][0]=fu[u];
	vv[u].pb(0);
	for(auto i:v[u]){
		dfs(i);
		siz[u]+=siz[i];
		if(siz[i]>maxx[u])mixx[u]=maxx[u],maxx[u]=siz[i];
		else if(siz[i]>mixx[u])mixx[u]=siz[i];
		vv[u].pb(siz[i]);
	}
	sort(vv[u].begin(),vv[u].end());
	sa[u].resize(vv[u].size()+1);
	sa[u][0]=vv[u][0];
	for(int i=1;i<(int)vv[u].size();i++)sa[u][i]=sa[u][i-1]+vv[u][i];
}
void solve(int u){
	ll tmp=siz[u];
	while(u){
		for(int i=18;i>=0;i--){
			if(tmp>=f[u][i]){
				tmp=tmp+s[u][i];
				u=g[u][i];
			}
		}
		if(u){
			ll pre=tmp;
			int tt=lower_bound(vv[fu[u]].begin(),vv[fu[u]].end(),pre)-vv[fu[u]].begin()-1;
			tmp=tmp+sa[fu[u]][tt]+(vv[fu[u]].size()-tt-1)*pre-pre;
			u=fu[u];
		}
	}
	print(tmp);
}
signed main(){
	#ifdef newbiewzs
	#else
	#endif
	st=clock();
	n=read();
	for(int i=1;i<=n;i++){
		fu[i]=read();a[i]=read();
		v[fu[i]].pb(i);
	}
	dfs(0);
	for(int i=1;i<=n;i++){
		f[i][0]=s[i][0]=siz[fu[i]]-a[fu[i]]-siz[i];
	}
	for(int i=1;i<=18;i++){
		for(int k=1;k<=n;k++){
			g[k][i]=g[g[k][i-1]][i-1];
			s[k][i]=(s[k][i-1]+s[g[k][i-1]][i-1]);
			f[k][i]=max(f[k][i-1],f[g[k][i-1]][i-1]-s[k][i-1]);
		}
	}
	
	for(int i=1;i<=n;i++){
		solve(i);
	}
	Flush();
	return 0;
}