MnZn树剖求调
查看原帖
MnZn树剖求调
649114
50lty12楼主2023/10/4 14:38

样例可过,提交全WA。

#include<bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N=1e5+5;
int n,q,k,a,b,tot=1,x,y,z;
int head[N],fa[N],son[N],sz[N],dep[N],top[N],seg[N],rev[N];
char op;
struct AB{
	int a,b,n;
}d[N];
struct SegmentTree{
	int l,r,sum,add;
}tr[N<<2];
void cun(int a,int b){
	d[++k].a=a,d[k].b=b;
	d[k].n=head[a],head[a]=k;
}
void dfs1(int u,int f){
	fa[u]=f;
	dep[u]=dep[f]+1;
	sz[u]=1;
	for(int i=head[u]; i; i=d[i].n){
		int v=d[i].b;
		if(v==f) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int f){
	if(son[u]){
		seg[son[u]]=++tot;
		rev[tot]=son[u];
		top[son[u]]=top[u];
		dfs2(son[u],u);
	}
	for(int i=head[u]; i; i=d[i].n){
		int v=d[i].b;
		if(top[v]) continue;
		seg[v]=++tot;
		rev[tot]=v;
		top[v]=v;
		dfs2(v,u);
	}
}
void pushup(int p){
	tr[p].sum=tr[lc].sum+tr[rc].sum;
}
void pushdown(int p){
	if(tr[p].add){
		tr[lc].sum+=(tr[lc].r-tr[lc].l+1)*tr[p].add;
		tr[rc].sum+=(tr[rc].r-tr[rc].l+1)*tr[p].add;
		tr[lc].add+=tr[p].add;
		tr[rc].add+=tr[p].add;
		tr[p].add=0;
	}
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){
		tr[p].sum=0;
		return;
	}
	int mid=l+r>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);	
	pushup(p);
} 
void change(int p,int x,int y,int v){
	if(tr[p].l>=x && tr[p].r<=y){
		tr[p].sum+=(tr[p].r-tr[p].l+1)*v;
		tr[p].add+=v;
		return;
	}
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1;
	if(x<=mid) change(lc,x,y,v);
	if(y>mid) change(rc,x,y,v);
	pushup(p);
}
int query(int p,int x,int y){
	if(tr[p].l>=x && tr[p].r<=y) return tr[p].sum;
	pushdown(p);
	int mid=tr[p].l+tr[p].r>>1,s=0;
	if(x<=mid) s+=query(lc,x,y);
	if(y>mid) s+=query(rc,x,y);
	return s;
}
void change_A(int x,int y,int z){
	int fx=top[x],fy=top[y];
	while(fx^fy){
		if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
		change(1,seg[fx],seg[x],z);
		x=fa[fx],fx=top[x];
	}
	if(dep[x]>dep[y]) swap(x,y);
	change(1,seg[x],seg[y],z);
}
signed main(){
	scanf("%lld",&n);
	for(int i=1; i<n; i++){
		scanf("%lld%lld",&a,&b);
		a++,b++;
		cun(a,b),cun(b,a);
	}
	dfs1(1,0);
	seg[1]=rev[1]=top[1]=1;
	dfs2(1,0);
	build(1,1,n);
	scanf("%lld",&q);
	while(q--){
		cin>>op;
		if(op=='A'){
			scanf("%lld%lld%lld",&x,&y,&z);
			x++,y++;
			change_A(x,y,z);
		}
		else{
			scanf("%lld",&x);
			x++;
			printf("%lld\n",query(1,seg[x],seg[x]+sz[x]-1));
		}
	}
	return 0;
}
2023/10/4 14:38
加载中...