萌新刚学树剖0.114514s,wa了5个求助,关注奉上
查看原帖
萌新刚学树剖0.114514s,wa了5个求助,关注奉上
524801
不食嗟来之食楼主2022/10/13 10:45
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+5;
int d[N],fa[N],top[N],idx[N],tot[N];
int cnt,n,q,son[N];
vector<int> e[N];
#define lson k<<1
#define rson k<<1|1
typedef long long _int;
struct peo {
	int l,r;
	long long sum,lazy;
} a[N<<2];
void push_up(int k) {
	a[k].sum=a[lson].sum+a[rson].sum;
}
void push_down(int k) {
	if(a[k].lazy) {
		a[lson].lazy+=a[k].lazy;
		a[rson].lazy+=a[k].lazy;
		a[lson].sum+=(a[lson].r-a[lson].l+1)*a[k].lazy;
		a[rson].sum+=(a[rson].r-a[rson].l+1)*a[k].lazy;
		a[k].lazy=0;
	}
	return ;
}
void dfs1(int u,int f) {
	d[u]=d[f]+1;
	tot[u]=1;
	fa[u]=f;
	for(auto v:e[u]) {
		dfs1(v,u);
		tot[u]+=tot[v];
		if(tot[v]>tot[son[u]])son[u]=v;
	}
	return ;
}
void dfs2(int u,int topf) {
	idx[u]=++cnt;
	top[cnt]=topf;
	if(!son[u]) {
		return ;
	} else dfs2(son[u],topf);
	for(auto v:e[u]) {
		if(!idx[v]) {
			dfs2(v,v);
		}
	}
}
void add(int k,int l,int r,_int val) {
	if(a[k].l>=l&&a[k].r<=r) {
		a[k].lazy+=val;
		a[k].sum+=(a[k].r-a[k].l+1)*val;
		return ;
	}
	push_down(k);
	int mid=(a[k].l+a[k].r)>>1;
	if(l<=mid) {
		add(lson,l,r,val);
	}
	if(r> mid) {
		add(rson,l,r,val);
	}
	push_up(k);
	return ;
}
_int sum(int k,int l,int r) {
	if(a[k].l>=l&&a[k].r<=r) {
		return a[k].sum;
	}
	push_down(k);
	_int ans=0;
	int mid=(a[k].l+a[k].r)>>1;
	if(l<=mid) ans+=sum(lson,l,r);
	if(r> mid) ans+=sum(rson,l,r);
	return ans;
}
void Ladd(int x,int y,_int val) {
	while(top[x]!=top[y]) {
		if(d[top[x]]<d[top[y]])swap(x,y);
		add(1,idx[top[x]],idx[x],val);
		x=fa[x];
	}
	if(d[x]>d[y])swap(x,y);
	add(1,idx[x],idx[y],val);
	return ;
}
void build(int k,int l,int r) {
	a[k].l=l,a[k].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(lson,l,mid);
	build(rson,mid+1,r);
	return ;
}
int main() {
	scanf("%d",&n);
	for(int i=1; i<n; i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		u++,v++;
		e[u].push_back(v);
	}
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	scanf("%d",&q);
	for(int i=1; i<=q; i++) {
		char opt;
		scanf(" %c",&opt);
		switch(opt) {
			case 'Q': {
					int x;
					scanf("%d",&x);
					x++;
					printf("%lld\n",sum(1,idx[x],idx[x]+tot[x]-1));
					break;
				}
			case 'A': {
					int x,y;
					_int val;
					scanf("%d%d%lld",&x,&y,&val);
					x++,y++;
					Ladd(x,y,val);
					break;
				}
		}
	}
}

rt ,球球各路大神了

2022/10/13 10:45
加载中...