自动搬运

查看原文

来自洛谷，原作者为

	gcx114514 你们都有光明的未来

搬运于2025-08-24 22:55:48，当前版本为作者最后更新于2024-11-21 19:31:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

很有意思的黑题，每一步都很自然。

思路

首先考虑如何比较两个点的删除时间，发现可以通过比较两个点删除时的票数来进行比较我们设 $dp_i$ 表示点 $i$ 被删除时的票数，

那么如果 $dp_x>dp_y$ 或者 $dp_x=dp_y$ 且 $x>y$ 那么 $x$ 比 $y$ 先删除。

注意到这是一个树形结构，每个人只会影响其祖先的票数，每个人的初始票数为 $a_x+\sum\limits_{v\in son(i)} b_v$，但是如果 $dp_v>dp_i$ 说明 $v$ 比 $i$ 先删除，那么 $dp_i\gets dp_i-b_v$，可以将儿子按照 $dp$ 值排序，令 $sum_{u,i}$ 表示 $u$ 排序完成的儿子的 $b$ 的前缀和，那么我们需要找到 $a_u+\sum b_v-sum_{u,i-1}<dp_{son_{u,i}}$ 即 $a_u+\sum b_i <sum_{u,i-1}+dp_{son_{u,i}}$，因为有修改，考虑用平衡树来维护，可以在上面二分得到答案，即维护前缀 ${sum_{u,i-1}+dp_{son_{u,i}}}$ 的最小值，这样有了 $O(n\log n+qd\log n)$ （其中 $d$ 表示树的深度）的做法。

考虑优化，每次修改是影响点 $u$ 到根这一条路径，考虑能否进行重剖进行优化。一个常用技巧：考虑对每个点只去维护其轻儿子的平衡树，考虑每次加入重儿子的贡献，在换链时作特殊处理。假设对于对于在轻儿子的平衡树上达到的答案是 $val$，如果 $val>dp_{son_u}$ 时可以知道 $u$ 一定在 $son_u$ 删除之前删除。否则应该用 $a_u+\sum b_v -b_{son_u}$ 到平衡树上二分得到答案。注意到这与每次更新与 $dp_{son_u}$ 没有关系，这是分段函数，可以用线段树维护，因为我们并没有考虑重儿子的情况，所以查询时要查询从我这开始到重链底部的贡献。现在的复杂度是 $O(n\log n+q\log^2 n)$ 的。

::::info[code]

#include <bits/stdc++.h>
#define pii pair<int,int>
#define pb emplace_back
#define mid ((l+r)>>1)
#define int long long
#define mk make_pair
#define rs now<<1|1
#define ls now<<1
#define reaD read
#define raed read
#define haed head
#define cotu cout
#define se second
#define fi first
#define itn int
using namespace std;
bool Mst;
const int Max=2e5+10;
const int mod=998244353;
const int inf=1e18+10;

inline int read(){
   int res=0,v=1;
   char c=getchar();
   while(c<'0'||c>'9'){v=(c=='-'?-1:1);c=getchar();}
   while(c>='0'&&c<='9'){res=(res<<3)+(res<<1)+(c^48);c=getchar();}
   return res*v;
}

int b[Max],dp[Max],sumb[Max];
int root[Max],Val[Max],n;

struct tree{
   int minn,sum,ch[2],key;
   #define ch(x,i) tr[x].ch[i] 
   #define minn(x) tr[x].minn
   #define sum(x) tr[x].sum
   #define key(x) tr[x].key
}tr[Max];

struct FHQ{  //平衡树编号与树的编号对应，方便处理 
   
   void pushup(int now){
   	sum(now)=sum(ch(now,0))+b[now]+sum(ch(now,1));
   	minn(now)=min(minn(ch(now,0)),min(sum(ch(now,0))+dp[now],sum(ch(now,0))+b[now]+minn(ch(now,1)))); 
   } 
   
   void Split(int now,pii val,int &x,int &y){
   	if(!now){x=y=0;return;}
   	if(dp[now]>val.fi||(dp[now]==val.fi&&now>val.se)){
   		x=now;
   		Split(ch(now,1),val,ch(x,1),y);
   	}else{
   		y=now;
   		Split(ch(now,0),val,x,ch(y,0));
   	}
   	pushup(now);
   } 
   
   int merge(int x,int y){
   	if(!x||!y)return x|y;
   	if(key(x)>key(y)){
   		ch(x,1)=merge(ch(x,1),y);
   		pushup(x);return x;
   	}else{
   		ch(y,0)=merge(x,ch(y,0));
   		pushup(y);return y;
   	}
   }
   
   int Query(int now,int val){
   	if(!now)return val;
   	if(minn(ch(now,0))<val)return Query(ch(now,0),val);
   	else if(sum(ch(now,0))+dp[now]<val)return val-sum(ch(now,0));
   	else return Query(ch(now,1),val-sum(ch(now,0))-b[now]);
   }
   void insert(int x,int y){
   	int xx,yy;
   	Split(root[x],mk(dp[y],y),xx,yy);
   	minn(y)=dp[y],sum(y)=b[y];key(y)=rand();
   	root[x]=merge(xx,merge(y,yy)); 
   }
   
   void Del(int x,int y){
   	int xx,yy,zz;
   	Split(root[x],mk(dp[y],y),xx,yy);
   	Split(yy,mk(dp[y],y-1),yy,zz);root[x]=merge(xx,zz);
   }

}t1;

struct Sg{
   int lim,x,y;//小于lim返回x,否则返回y
   Sg(int lim=0,int x=0,int y=0):
   	lim(lim),x(x),y(y){;}
   int chk(int z){return z<lim?x:y;}
    
   Sg operator +(Sg b){return Sg(lim,b.chk(x),b.chk(y));}
}f[Max];  //每个点的函数 


struct SGT{  //线段树维护分段函数。 
   
   Sg tr[Max<<2];
   
   void pushup(int now){
   	tr[now]=tr[now<<1|1]+tr[now<<1];
   }
    
   void Modify(int now,int l,int r,int to,Sg val){
   	if(l==r){tr[now]=val;return;}
   	if(to<=mid)Modify(ls,l,mid,to,val);
   	else Modify(rs,mid+1,r,to,val);
   	pushup(now);
   }
   
   Sg Query(int now,int l,int r,int L,int R){
   	if(L<=l&&R>=r)return tr[now];
   	if(R<=mid)return Query(ls,l,mid,L,R);
   	if(L>mid)return Query(rs,mid+1,r,L,R);
   	return Query(rs,mid+1,r,L,R)+Query(ls,l,mid,L,R);
   }
}t2;

struct Node{
   int to,next;
   Node(int to=0,int next=0):
   	to(to),next(next){;}
}a[Max<<1];
int head[Max],cnt;
void add(int x,int y){
   a[++cnt]=Node(y,head[x]);
   head[x]=cnt;
}

struct Tree{
   int siz,son,dep,fa,id,end,top;
   #define siz(x) bbb[x].siz
   #define top(x) bbb[x].top
   #define son(x) bbb[x].son
   #define dep(x) bbb[x].dep
   #define end(x) bbb[x].end
   #define id(x) bbb[x].id
   #define fa(x) bbb[x].fa 
}bbb[Max];

Sg Queryf(int now){
   if(!son(now))return Sg(0,0,Val[now]);
   int val=t1.Query(root[now],Val[now]+sumb[now]); //轻儿子的值。 
   return Sg(val,val,t1.Query(root[now],Val[now]+sumb[now]-b[son(now)]));
} 

void dfs1(int now,int fa){
   siz(now)=1;fa(now)=fa;dep(now)=dep(fa)+1;
   for(int i=head[now];i;i=a[i].next){
   	int to=a[i].to;
   	if(to==fa)continue;
   	sumb[now]+=b[to];
   	dfs1(to,now);siz(now)+=siz(to);
   	son(now)=siz(son(now))>siz(to)?son(now):to;
   } 
   
   for(int i=head[now];i;i=a[i].next){
   	int to=a[i].to;
   	if(to==fa||to==son(now))continue;
   	t1.insert(now,to); 
   }
   f[now]=Queryf(now);dp[now]=f[now].chk(dp[son(now)]); 
} 

int Res=0;

void dfs2(int now,int top){
   id(now)=++Res;top(now)=top;t2.Modify(1,1,n,id(now),f[now]); 
   if(son(now)){
   	dfs2(son(now),top);end(now)=end(son(now));
   }else end(now)=now;   //记录链底 
   for(int i=head[now];i;i=a[i].next){
   	int to=a[i].to;
   	if(!id(to))dfs2(to,to);
   } 
}

void work(int x,int opt=-1){
   t1.Del(fa(x),x);
   if(opt!=-1)b[x]=opt;
   dp[x]=t2.Query(1,1,n,id(x),id(end(x))).chk(0);
   t1.insert(fa(x),x);
}

void Modify(int x){
   while(x){
   	f[x]=Queryf(x);t2.Modify(1,1,n,id(x),f[x]);
   	x=top(x);
   	if(x!=1){work(x);}
   	else return ;
   	x=fa(x);
   }
}

bool Med;
signed main(){n=read();
   n=read();int q=read();
   for(int i=2;i<=n;++i)add(read(),i);
   for(int i=1;i<=n;++i)Val[i]=read();
   for(int i=1;i<=n;++i)b[i]=read(); 
   minn(0)=inf;
   dfs1(1,0);
   dfs2(1,1);
   for(int i=1;i<=q;++i){
   	int opt=read();
   	if(opt==1){
   		int p,x,y;
   		p=read(),x=read(),y=read();
   		Val[p]=x;Modify(p);
   		if(p!=1){
   			sumb[fa(p)]-=b[p];sumb[fa(p)]+=y;
   			if(p!=son(fa(p)))work(p,y);
   			b[p]=y;
   			Modify(fa(p));
   		}
   	}else{
   		int x,y;
   		x=read(),y=read();
   		int tag=x>y; 
   		x=t2.Query(1,1,n,id(x),id(end(x))).chk(0);
   		y=t2.Query(1,1,n,id(y),id(end(y))).chk(0);
   		if(x>y||((x==y)&&(tag)))cout << 0 << "\n";
   		else cout << 1 << "\n";
   	}
   }
   cerr<< "Time: "<<clock()/1000.0 << "s\n";
   cerr<< "Memory: " << (&Med-&Mst)/1000000.0 << "MB\n";
   return 0;
}

::::