求助3833树链剖分,50,WA,悬关
查看原帖
求助3833树链剖分,50,WA,悬关
931707
017_007楼主2023/9/14 17:14
#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read(){
	int x=0,f=1;char s=getchar();
	while (s>'9'||s<'0'){
		if (s=='-') f=-f;
		s=getchar();
	}
	while (s>='0'&&s<='9') {
		x=(x<<1)+(x<<3)+(s^48);
		s=getchar();
	}
	return x*f;
}

const int N = 1e5+10;

int n,u,v,first[N],cnt,m,x,y,z,sum[N<<2],lazy[N<<2];
int fa[N],dep[N],num[N],zson[N],st[N],nid[N],dnow;
char op;
struct edge{
	int to,nxt;
}edges[N<<1];

void add(int u,int v){
	edges[++cnt].to=v;
	edges[cnt].nxt=first[u];
	first[u]=cnt;
}

void dfs1(int root,int last){
	fa[root]=last;num[root]=1;dep[root]=dep[last]+1;
	for (int t=first[root];t;t=edges[t].nxt){
		int h=edges[t].to;
		if (h==last) continue;
		dfs1(h,root);
		num[root]+=num[h];
		if (num[h]>num[zson[root]]) zson[root]=h;
	}
}

void dfs2(int root,int topx){
	nid[root]=++dnow;
	st[root]=topx;
	if (!zson[root]) return;
	dfs2(zson[root],topx);
	for (int t=first[root];t;t=edges[t].nxt){
		int h=edges[t].to;
		if (h==fa[root]||h==zson[root]) continue;
		dfs2(h,h);
	}
}

void Add(int k,int l,int r,int v){
	sum[k]+=(r-l+1)*v;
	lazy[k]+=v;
}

void pushdown(int k,int l,int r){
	if (!lazy[k]) return;
	int mid=(l+r)>>1;
	Add(k<<1,l,mid,lazy[k]);
	Add(k<<1|1,mid+1,r,lazy[k]);
	lazy[k]=0;return;
}

void modify(int k,int l,int r,int zl,int zr,int v){
	if (l>=zl&&r<=zr) {
		Add(k,l,r,v);
		return;
	}
	pushdown(k,l,r);
	int mid=(l+r)>>1;
	if (mid>=zl) modify(k<<1,l,mid,zl,zr,v);
	if (mid<zr) modify(k<<1|1,mid+1,r,zl,zr,v);
	sum[k]=sum[k<<1]+sum[k<<1|1];
	return;
}

int ser(int k,int l,int r,int zl,int zr){
	if (l>=zl&&r<=zr) return sum[k];
	pushdown(k,l,r);
	int mid=(l+r)>>1,res=0;
	if (mid>=zl) res+=ser(k<<1,l,mid,zl,zr);
	if (mid<zr) res+=ser(k<<1|1,mid+1,r,zl,zr);
	return res;
}

void add_path(int x,int y){
	int d1=x,d2=y;
	while (st[d1]!=st[d2]){
		if (dep[st[d1]]<dep[st[d2]]) swap(d1,d2);
		modify(1,1,n,nid[d1],nid[st[d1]],z);
		d1=fa[st[d1]];
	}
	int l=min(nid[d1],nid[d2]),r=max(nid[d1],nid[d2]);
	modify(1,1,n,l,r,z);
}

signed main(){	
	n=read();
	for (int i=1;i<n;++i) u=read(),v=read(),add(u+1,v+1),add(v+1,u+1);
	dfs1(1,0);dfs2(1,1);
	m=read();
	while (m--){
		cin>>op;
		if (op=='A'){
			x=read();y=read();z=read();
			++x;++y;
			add_path(x,y);
		}
		else {
			x=read();
			++x;
			printf("%lld\n",ser(1,1,n,nid[x],nid[x]+num[x]-1));
		}
	}
	return 0;
}
2023/9/14 17:14
加载中...