求助树剖+线段树全WA(
查看原帖
求助树剖+线段树全WA(
214728
剑雪清寒楼主2022/4/29 20:08

rt

#include <bits/stdc++.h>
using namespace std;
inline long long read() {
	long long x,f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x;
}
int cnt;
struct node {
	int dfn,deep,dad,wson,top,size;
}nd[100001];
int rs;
struct edge {
	int to;
	edge *gone;
}rd[200001];
edge *head[100001];
struct litree {
	long long sum[200001],lazy[200001];
	int lson[1<<18],rson[1<<18],s;
	inline void update(int x) { sum[x]=sum[lson[x]]+sum[rson[x]]; }
	inline void lad(int x,int l,int r) {
		int mid=(l+r)>>1;
		sum[lson[x]]+=lazy[x]*(mid-l+1);
		sum[rson[x]]+=lazy[x]*(r-mid);
		lazy[lson[x]]+=lazy[x];
		lazy[rson[x]]+=lazy[x];
		lazy[x]=0;
		return ;
	}
	inline void build(int ss,int l,int r) {
		s++;
		if(l==r) return ;
		int mid=(l+r)>>1;
		lson[ss]=s+1;
		build(s+1,l,mid);
		rson[ss]=s+1;
		build(s+1,mid+1,r);
		return ;
	}
	inline void ad(int x,int l,int r,int L,int R,long long as) {
		if(r<L || l>R) return ;
		if(l>=L && r<=R) {
			sum[x]+=as*(r-l+1);
			lazy[x]+=as;
			return ;
		}
		lad(x,l,r);
		int mid=(l+r)>>1;
		ad(lson[x],l,mid,L,R,as);
		ad(rson[x],mid+1,r,L,R,as);
		update(x);
		return ;
	}
	inline long long check(int x,int l,int r,int L,int R) {
		if(r<L || l>R) return 0;
		if(l>=L && r<=R) return sum[x];
		lad(x,l,r);
		int mid=(l+r)>>1;long long a,b;
		a=check(lson[x],l,mid,L,R);
		b=check(rson[x],mid+1,r,L,R);
		update(x);
		return a+b;
	}
}tree;
inline void dfs1(int x,int dep) {
	nd[x].deep=dep;nd[x].size=1;
	for(edge *i=head[x];i!=NULL;i=i->gone) {
		int nex=i->to;
		nd[nex].dad=x;
		dfs1(nex,dep+1);
		nd[x].size+=nd[nex].size;
		if(nd[nex].size>nd[nd[x].wson].size) nd[x].wson=nex;
	}
	return ;
}
inline void dfs2(int x,int tp) {
	nd[x].top=tp;nd[x].dfn=++cnt;
	if(nd[x].wson) dfs2(nd[x].wson,tp);
	for(edge *i=head[x];i!=NULL;i=i->gone) {
		int nex=i->to;
		if(nex==nd[x].wson) continue;
		dfs2(nex,nex);
	}
	return ;
}
int n=read();
inline void add(int u,int v,int as) {
	while(nd[u].top!=nd[v].top) {
		if(nd[u].top<nd[v].top) swap(u,v);
		tree.ad(1,1,n,nd[nd[u].top].dfn,nd[u].dfn,as);
		u=nd[nd[u].top].dad;
	}
	if(nd[u].deep>nd[v].deep) swap(u,v);
	tree.ad(1,1,n,nd[u].dfn,nd[v].dfn,as);
	return ;
}
int main() {
	for(int i=1;i<n;i++) {
		int u=read()+1,v=read()+1;
		rd[rs].to=v;rd[rs].gone=head[u];
		head[u]=&rd[rs++];
	}
	dfs1(1,1);
	dfs2(1,1);
	tree.build(1,1,n);
	int Q=read();
	while(Q--) {
		char k=getchar();
		if(k=='A') {
			int u=read()+1,v=read()+1,d=read();
			add(u,v,d);
		}
		else {
			int u=read()+1;
			printf("%lld\n",tree.check(1,1,n,nd[u].dfn,nd[u].dfn+nd[u].size-1));
		}
	}
	return 0;
}
2022/4/29 20:08
加载中...