rt

试这个做法主要是因为跑不满。

思路是一个点到根的答案 $\times2$ 的次数最多62次，所以暴力跳到需要 $\times2$ 的点。$sum[u]$ 为从 $u$ 到根答案贡献如果全部为加，加起来的和。一个点 $v$ 对于当前点 $u$ 如果会 $\times2$，那么 $val+sum[u]-sum[v]<siz[brother(v)]$，其中 $val$ 为当前答案，得 $val+sum[u]<sum[v]+siz[brother(v)]$。开一棵权值线段数求满足上式得深度最大 $v$。

是细节问题还是本身做法有bug？（不管TLE）

蒟蒻请求大佬指出

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e6+10;
ll n,fa[maxn],c[maxn],ch[maxn][2],siz[maxn],sum[maxn],mn[maxn*4],h[maxn],ht,w[maxn],ans[maxn],dep[maxn];
ll Min(ll u,ll v)
{
	return dep[u]>dep[v]?u:v;
}
void modify(ll p,ll l,ll r,ll x,ll v)
{
	if(l==r)
	{
		mn[p]=v;
		return;
	}
	ll mid=l+r>>1;
	if(x<=mid) modify(p<<1,l,mid,x,v);
	else modify(p<<1|1,mid+1,r,x,v);
	mn[p]=Min(mn[p<<1],mn[p<<1|1]);
}
ll query(ll p,ll l,ll r,ll ql)
{
	if(ql<=l) return mn[p];
	if(r<ql) return 0;
	ll mid=l+r>>1;
	return Min(query(p<<1,l,mid,ql),query(p<<1|1,mid+1,r,ql));
}
void dfs(ll u)
{
	if(ch[u][0]) dep[ch[u][0]]=dep[u]+1,dfs(ch[u][0]);
	if(ch[u][1]) dep[ch[u][1]]=dep[u]+1,dfs(ch[u][1]);
	siz[u]=c[u]+siz[ch[u][0]]+siz[ch[u][1]];
}
void dfss(ll u)
{
	if(ch[u][0]&&ch[u][1])
	{
		sum[ch[u][0]]=sum[u]+siz[ch[u][1]];
		sum[ch[u][1]]=sum[u]+siz[ch[u][0]];
		dfss(ch[u][0]); dfss(ch[u][1]);
		h[++ht]=sum[ch[u][0]]+siz[ch[u][1]];
		h[++ht]=sum[ch[u][1]]+siz[ch[u][0]];
	}
	else if(ch[u][0]) sum[ch[u][0]]=sum[u],dfss(ch[u][0]);
	else if(ch[u][1]) sum[ch[u][1]]=sum[u],dfss(ch[u][1]);
}
void solve(ll u)
{
	ll val=siz[u],uu=u;
	while(u>1)
	{
		ll tmp=0,q=upper_bound(h+1,h+1+ht,val+sum[u])-h;
		tmp=query(1,1,ht,q);
		val+=sum[u]-sum[w[tmp]];
		if(w[tmp]) val<<=1;
		u=fa[w[tmp]];
	}
	ans[uu]=val;
}
void dfs2(ll u)
{
	if(ch[u][0]&&ch[u][1])
	{
		ll tmp,g;
		tmp=lower_bound(h+1,h+1+ht,sum[ch[u][0]]+siz[ch[u][1]])-h,g=w[tmp];
		w[tmp]=ch[u][0];
		modify(1,1,ht,tmp,ch[u][0]);
		dfs2(ch[u][0]);
		w[tmp]=g;
		modify(1,1,ht,tmp,g);
		tmp=lower_bound(h+1,h+1+ht,sum[ch[u][1]]+siz[ch[u][0]])-h,g=w[tmp];
		w[tmp]=ch[u][1];
		modify(1,1,ht,tmp,ch[u][1]);
		dfs2(ch[u][1]);
		w[tmp]=g;
		modify(1,1,ht,tmp,g);
		solve(u);
	}
	else if(ch[u][0]) dfs2(ch[u][0]);
	else if(ch[u][1]) dfs2(ch[u][1]);
	solve(u);
}
int main()
{
	scanf("%lld",&n);
	for(ll i=2;i<=n;i++)
	{
		scanf("%lld",&fa[i]);
		ch[fa[i]][ch[fa[i]][0]>1]=i;
	}
	for(ll i=1;i<=n;i++) scanf("%lld",&c[i]);
	dep[1]=1;
	dfs(1);
	dfss(1);
	sort(h+1,h+1+ht);
	ht=unique(h+1,h+1+ht)-h-1;
	dfs2(1);
	for(ll i=1;i<=n;i++)
	{
		printf("%lld ",ans[i]);
	}
	return 0;
}