树剖WA4-5个点求调
查看原帖
树剖WA4-5个点求调
631550
liuziqin楼主2023/12/2 15:39
#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
int n,w[maxn];
int cur,h[maxn],nxt[maxn],p[maxn];
int siz[maxn],top[maxn],son[maxn],dep[maxn],fa[maxn],dfn[maxn],rnk[maxn],cnt,mod;
void add_edge(int x,int y){  // 加边
  cur++;
  nxt[cur]=h[x];
  h[x]=cur;
  p[cur]=y;
}
struct SegTree{
	int sum[maxn*4],si[maxn*4],lazy[maxn*4];
	void pushup(int p){
		sum[p]=sum[p*2]+sum[p*2+1];
		si[p]=si[p*2]+si[p*2+1];
	}
	void a_lazy(int p,int v){
		lazy[p]+=v;
		sum[p]+=v*si[p];
	}
	void push_down(int p){
		a_lazy(p*2,lazy[p]);
		a_lazy(p*2+1,lazy[p]);
		lazy[p]=0;
	}
	void build(int p,int l,int r){
	    if(l==r){
	    	sum[p]=w[rnk[l]];
	    	si[p]=1;
			return;
	    }
	    int mid=(l+r)>>1;
	    build(p*2,l,mid);
	    build(p*2+1,mid+1,r);
	    pushup(p);
	}
	int query(int p,int l,int r,int x, int y){
		if(l>=x&&r<=y)return sum[p];
	    int mid=(l+r)>>1,ans=0;
	    push_down(p);
	    if(mid>=x)ans+=query(p*2,l,mid,x,y);
	    if(mid<y)ans+=query(p*2+1,mid+1,r,x,y);
	    return ans;
	}
	void add(int p,int l,int r,int x,int y,int v){
	  	if(l>=x&&r<=y){
	  		a_lazy(p,v);
	  		return;
		}
		int mid=(l+r)>>1;
		push_down(p);
		if(mid>=x)add(p*2,l,mid,x,y,v);
		if(mid<y)add(p*2+1,mid+1,r,x,y,v);
		pushup(p);
	}
}st;
void dfs1(int x){
	son[x]=-1;
  	siz[x]=1;
	for(int j=h[x];j;j=nxt[j])
	if(!dep[p[j]]){
	   	fa[p[j]]=x;
	 	dep[p[j]]=dep[x]+1;
	   	dfs1(p[j]);
	   	siz[x]+=siz[p[j]];
	   	if(son[x]==-1||siz[p[j]]>siz[son[x]])son[x]=p[j];
	}
}
void dfs2(int x,int t){
	top[x]=t;
	cnt++;
	dfn[x]=cnt;
	rnk[cnt]=x;
	if(son[x]==-1)return;
	dfs2(son[x],t);
	for(int j=h[x];j;j=nxt[j])
	if(p[j]!=son[x]&&p[j]!=fa[x])dfs2(p[j],p[j]);
}
int querysum(int x,int y){
	int ret=0,fx=top[x],fy=top[y];
	while(fx!=fy){
	    if(dep[fx]>=dep[fy])ret+=st.query(1,1,n,dfn[fx],dfn[x]),x=fa[fx];
	    else ret+=st.query(1,1,n,dfn[fy],dfn[y]),y=fa[fy];
	    fx=top[x];
	    fy=top[y];
	}
	if(dfn[x]<dfn[y])ret+=st.query(1,1,n,dfn[x],dfn[y]);
	else ret+=st.query(1,1,n,dfn[y],dfn[x]);
	return ret;
}
void addsum(int x,int y,int v){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(dep[fx]>=dep[fy])st.add(1,1,n,dfn[fx],dfn[x],v),x=fa[fx];
		else st.add(1,1,n,dfn[fy],dfn[y],v),y=fa[fy];
		fx=top[x];
		fy=top[y];
	}
	if(dfn[x]<dfn[y])st.add(1,1,n,dfn[x],dfn[y],v);
	else st.add(1,1,n,dfn[y],dfn[x],v);
}
signed main(){
	int q;
	cin>>n>>q>>w[1];
	for(int i=2;i<=n;i++){
		int a;
		cin>>w[i]>>a;
		add_edge(a,i);
	}
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	st.build(1,1,n);
	while(q--){
	  	int x,z;
	  	char op;
	  	cin>>op>>x;
	  	if(op=='p'){
	  		cin>>z;
	  		st.add(1,1,n,dfn[x]+1,dfn[x]+siz[x]-1,z);
		}
		else cout<<st.query(1,1,n,dfn[x],dfn[x])<<endl;
	}
}
2023/12/2 15:39
加载中...