自动搬运

查看原文

来自洛谷，原作者为

	gxy001 ......

搬运于2025-08-24 22:54:20，当前版本为作者最后更新于2024-01-27 18:35:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

建出 fail 树，称原字典树为 $T1$，fail 树为 $T2$，则所求为，对于每个点 $u$：

$$\sum\limits_{x\in path_{T1}(rt,u)}\max\limits_{dep_{T1}(x)\ge a_v\land v\in subtree_{T2}(u)\land v\in subtree_{T1}(x)}val_v $$

注意到 $dep_{T1}(x)\ge a_v\land v\in subtree_{T1}(x)$ 等价于 $x\in path_{T1}(p_v,v)$（$p_v$ 为 $v$ 的深度为 $a_v$ 的祖先）。

因此，所求可转化为：

$$\sum\limits_{x\in path_{T1}(rt,u)}\max\limits_{x\in path_{T1}(p_v,v)\land v\in subtree_{T2}(u)}val_v $$

我们使用数据结构维护 $T1$，对 $subtree_{T2}(u)$ 内的每个点 $v$，对链 $path_{T1}(p_v,v)$ 上每个点与 $val_v$ 取 $\max$，然后再求和 $path_{T1}(rt,u)$，即为答案。

链取 $max$，链和，可以使用静态 top tree beats 完成。而我们要对 $u$ 子树内的每个点 $v$ 都执行一个只和 $v$ 有关的修改，不难想到可以使用静态 top tree 合并来维护。

另外，本题为二叉树，这使得每个点最多只有一个虚儿子，利用这点可以使维护更简单。本题的时空限制都较紧，务必注意实现的常数。

时间复杂度为 $O(n\log n)$。

#include<iostream>
#include<algorithm>
#include<vector>
#define BUFSIZE 10000000
struct read{
	char buf[BUFSIZE],*p1,*p2,c;
	read():p1(buf),p2(buf){}
	char gc(void){
		return p1==p2&&(p2=buf+fread(p1=buf,1,BUFSIZE,stdin),p1==p2)?EOF:*p1++;
	}
	read& operator >>(int& x){
		for(c=gc(),x=0;c<'0'||c>'9';c=gc());
		for(;c>='0'&&c<='9';c=gc())x=x*10+(c-'0');
		return *this;
	}
}cin;
struct write{
	char buf[BUFSIZE],*p1,*p2;
	write():p1(buf),p2(buf+BUFSIZE){}
	~write(){fwrite(buf,1,p1-buf,stdout);}
	void pc(char c){p1==p2&&(fwrite(buf,1,p1-buf,stdout),p1=buf),*p1++=c;}
	write& operator <<(long long x){
		static int stk[30],tp;
		do stk[tp++]='0'+x%10,x/=10; while(x);
		while(tp) pc(stk[--tp]);
		return *this;
	}
	write& operator <<(char c){return pc(c),*this;}
}cout;
int n,s[500010][2],fail[500010];
int val[500010],a[500010],p[500010];
namespace TT{
	int rt,cnt,sz[1000010],csz[1000010],A[1000010],B[1000010],ls[500010],rs[500010],tp[500010];
	int s[500010],fa[500010],son[500010];
	int newnode(int x){
		int u=x+n;
		csz[u]=sz[u]=1,A[u]=B[u]=x;
		return u;
	}
	int bd(int x,int y,int p){
		int u=++cnt;
		ls[u]=x,rs[u]=y,sz[u]=sz[x]+sz[y],tp[u]=p;
		if(p==0) csz[u]=csz[x]+csz[y],A[u]=A[x],B[u]=B[y];
		else csz[u]=csz[x],A[u]=A[x],B[u]=B[x];
		return u;
	}
	int c[500010],cs[500010],ccnt;
	int cbuild(int l,int r,int p){
		if(l==r) return c[l];
		int u=std::lower_bound(cs+l,cs+r,cs[l-1]+(cs[r]-cs[l-1])/2)-cs;
		if(u==r) return bd(cbuild(l,r-1,p),c[r],p);
		else return bd(cbuild(l,u,p),cbuild(u+1,r,p),p);
	}
	int build(int x){
		int u=x;
		static int tmp[500010];
		while(u){
			for(auto w: ::s[u])if(w&&w!=son[u]) tmp[w]=build(w);
			ccnt=0,c[++ccnt]=newnode(u),cs[ccnt]=1;
			for(auto w: ::s[u])if(w&&w!=son[u]) c[++ccnt]=tmp[w],cs[ccnt]=cs[ccnt-1]+sz[tmp[w]];
			tmp[u]=cbuild(1,ccnt,1),u=son[u];
		}
		u=x,ccnt=0;
		while(u) c[++ccnt]=tmp[u],cs[ccnt]=cs[ccnt-1]+sz[tmp[u]],u=son[u];
		return cbuild(1,ccnt,0);
	}
	int R[1000010],ct;
	void ini(int x){
		if(x>n) return A[x]=B[x]=R[x]=++ct,void();
		ini(ls[x]),ini(rs[x]);
		A[x]=A[A[x]+n],B[x]=B[B[x]+n];
		R[x]=ct;
	}
	void dfs(int x){
		static int pt,f[500010];
		f[pt++]=x,s[x]=1,son[x]=0;
		if(a[x]>=pt) p[x]=0;
		else p[x]=f[a[x]];
		for(int u: ::s[x]) if(u) fa[u]=x,dfs(u),s[x]+=s[u],son[x]=(s[son[x]]>s[u]?son[x]:u);
		--pt;
	}
	void init(){
		cnt=0;
		dfs(1);
		rt=build(1);
		ini(rt);
	}
}
std::vector<int> vec[500010];
int sz[500010];
void dfs(int x){
	sz[x]=1;
	for(auto u:vec[x]) dfs(u),sz[x]+=sz[u];
}
long long ans[500010];
#define MAXN 2100010
int cct,ls[MAXN],rs[MAXN],mn[MAXN],lmn[MAXN],cnt[MAXN],tag[MAXN];
long long sum[MAXN],stk[MAXN],tp;
inline int newnode(int pos){
	using TT::csz;
	int u=tp?stk[--tp]:++cct;
	ls[u]=rs[u]=0,tag[u]=sum[u]=mn[u]=0,cnt[u]=csz[pos],lmn[u]=2e9;
	return u;
}
inline void addtag(int x,int v){
	sum[x]+=1ll*(v-mn[x])*cnt[x];
	mn[x]=tag[x]=v;
}
inline void pushdown(int x,int pos){
	if(!tag[x]) return;
	if(!ls[x]) ls[x]=newnode(TT::ls[pos]);
	if(TT::tp[pos]==0){
		if(!rs[x]) rs[x]=newnode(TT::rs[pos]);
		if(mn[ls[x]]==mn[rs[x]]) addtag(ls[x],tag[x]),addtag(rs[x],tag[x]);
		else if(mn[ls[x]]<mn[rs[x]]) addtag(ls[x],tag[x]);
		else addtag(rs[x],tag[x]);
	}else addtag(ls[x],tag[x]);
	tag[x]=0;
}
inline void pushup(int x,int pos){
	using TT::csz;
	if(TT::tp[pos]==0){
		if(!ls[x]&&!rs[x]) sum[x]=mn[x]=0,cnt[x]=csz[pos],lmn[x]=2e9;
		else if(!ls[x]) sum[x]=sum[rs[x]],mn[x]=0,lmn[x]=(mn[rs[x]]==0?lmn[rs[x]]:mn[rs[x]]),cnt[x]=csz[TT::ls[pos]]+(mn[rs[x]]==0?cnt[rs[x]]:0);
		else if(!rs[x]) sum[x]=sum[ls[x]],mn[x]=0,lmn[x]=(mn[ls[x]]==0?lmn[ls[x]]:mn[ls[x]]),cnt[x]=csz[TT::rs[pos]]+(mn[ls[x]]==0?cnt[ls[x]]:0);
		else{
			if(mn[ls[x]]==mn[rs[x]]) sum[x]=sum[ls[x]]+sum[rs[x]],mn[x]=mn[ls[x]],lmn[x]=std::min(lmn[ls[x]],lmn[rs[x]]),cnt[x]=cnt[ls[x]]+cnt[rs[x]];
			else if(mn[ls[x]]<mn[rs[x]]) sum[x]=sum[ls[x]]+sum[rs[x]],mn[x]=mn[ls[x]],lmn[x]=std::min(lmn[ls[x]],mn[rs[x]]),cnt[x]=cnt[ls[x]];
			else sum[x]=sum[ls[x]]+sum[rs[x]],mn[x]=mn[rs[x]],lmn[x]=std::min(mn[ls[x]],lmn[rs[x]]),cnt[x]=cnt[rs[x]];
		}
	}else
		if(!ls[x]) sum[x]=mn[x]=0,cnt[x]=csz[pos],lmn[x]=2e9;
		else sum[x]=sum[ls[x]],mn[x]=mn[ls[x]],cnt[x]=cnt[ls[x]],lmn[x]=lmn[ls[x]];
}
inline void beats(int &rt,int v,int pos){
	if(!rt) rt=newnode(pos);
	if(v<=mn[rt]) return;
	if(v<lmn[rt]) return addtag(rt,v);
	tag[rt]=0;
	beats(ls[rt],v,TT::ls[pos]),beats(rs[rt],v,TT::rs[pos]);
	pushup(rt,pos);
}
inline void lupdate(int b,int v,int &rt,int pos=TT::rt){
	using TT::B,TT::R;
	if(!rt) rt=newnode(pos);
	if(B[pos]==b) return beats(rt,v,pos);
	pushdown(rt,pos);
	if(b<=R[TT::ls[pos]]) lupdate(b,v,ls[rt],TT::ls[pos]);
	else beats(ls[rt],v,TT::ls[pos]),lupdate(b,v,rs[rt],TT::rs[pos]);
	pushup(rt,pos);
}
inline void rupdate(int a,int v,int &rt,int pos=TT::rt){
	using TT::A,TT::R;
	if(!rt) rt=newnode(pos);
	if(A[pos]==a) return beats(rt,v,pos);
	pushdown(rt,pos);
	if(a>R[TT::ls[pos]]) rupdate(a,v,rs[rt],TT::rs[pos]);
	else rupdate(a,v,ls[rt],TT::ls[pos]),beats(rs[rt],v,TT::rs[pos]);
	pushup(rt,pos);
}
inline void update(int a,int b,int v,int &rt,int pos=TT::rt){
	using TT::A,TT::B,TT::R;
	if(!rt) rt=newnode(pos);
	if(A[pos]==a&&B[pos]==b) return beats(rt,v,pos);
	pushdown(rt,pos);
	if(b<=R[TT::ls[pos]]) update(a,b,v,ls[rt],TT::ls[pos]);
	else if(a>R[TT::ls[pos]]) update(a,b,v,rs[rt],TT::rs[pos]);
	else rupdate(a,v,ls[rt],TT::ls[pos]),lupdate(b,v,rs[rt],TT::rs[pos]);
	pushup(rt,pos);
}
inline long long query(int b,int rt,int pos=TT::rt){
	using TT::B,TT::R;
	if(!rt) return 0;
	if(B[pos]==b)return sum[rt];
	pushdown(rt,pos);
	if(b<=R[TT::ls[pos]]) return query(b,ls[rt],TT::ls[pos]);
	else return sum[ls[rt]]+query(b,rs[rt],TT::rs[pos]);
}
void merge(int &x,int y,int pos=TT::rt){
	using TT::A,TT::B;
	if(!x||!y) return x|=y,void();
	if(pos>n) return sum[x]=mn[x]=std::max(mn[x],mn[y]),stk[tp++]=y,void();
	int u=std::max(tag[x],tag[y]);
	tag[x]=0;
	merge(ls[x],ls[y],TT::ls[pos]);
	merge(rs[x],rs[y],TT::rs[pos]);
	pushup(x,pos);
	if(u) beats(x,u,pos);
	stk[tp++]=y;
}
int solve(int x){
	int rt=0;
	std::sort(vec[x].begin(),vec[x].end(),[&](int x,int y){return sz[x]>sz[y];});
	for(auto u:vec[x]) merge(rt,solve(u));
	if(p[x]==1) lupdate(TT::A[x+n],val[x],rt);
	else if(p[x]) update(TT::A[p[x]+n],TT::A[x+n],val[x],rt);
	ans[x]=query(TT::A[x+n],rt);
	return rt;
}
#include<chrono>
using namespace std::chrono_literals;
void solve(){
	auto u=std::chrono::steady_clock().now();
	cin>>n;
	for(int i=1;i<=n;i++) s[i][0]=s[i][1]=fail[i]=0,vec[i].clear(),vec[i].shrink_to_fit();
	for(int i=2,x,v;i<=n;i++) cin>>x>>v,s[x][v]=i;
	for(int i=1;i<=n;i++) cin>>val[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	TT::init();
	static int que[500010];
	int *hd=que,*tl=que;
	for(int i=0;i<2;i++) if(s[1][i]) *tl++=s[1][i],fail[s[1][i]]=1;else s[1][i]=1;
	while(hd!=tl){
		int p=*hd++;
		for(int i=0;i<2;i++)
			if(s[p][i]) fail[s[p][i]]=s[fail[p]][i],*tl++=s[p][i];
			else s[p][i]=s[fail[p]][i];
	}
	for(int i=2;i<=n;i++) vec[fail[i]].push_back(i);
	dfs(1);
	cct=tp=0,lmn[0]=2e9;
	solve(1);
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	cout<<'\n';
	std::cerr<<cct<<' '<<(std::chrono::steady_clock().now()-u)/1.0s<<'\n';
}
int main(){
	int T;
	cin>>T;	
	while(T--) solve();
	return 0;
}