所有点RE,样例过,求助
查看原帖
所有点RE,样例过,求助
225048
ghr_226楼主2020/5/8 21:12

RT

#include<bits/stdc++.h>
using namespace std;
#define in Read()
#define re register
#define int long long
#define lch p<<1
#define rch p<<1|1

inline char ch(){
	static char buf[1<<21],*p1=buf,*p2=buf;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}

inline int in{
	int s=0,f=1;char x;
	for(x=getchar();x<'0'||x>'9';x=getchar())	if(x=='-')	f=-1;
	for( ;x>='0'&&x<='9';x=getchar())	s=(s*10)+(x&15);
	return f==1?s:-s;
}

//编号+1 
const int A=1e6+5;
int n,q;
int head[A],tot_road;
struct Road{
	int nex,to;
}road[2*A];
inline void ljb(int x,int y){
	road[++tot_road]={head[x],y};head[x]=tot_road;
}
int f[A],dep[A],size[A],son[A],top[A],pos[A],idx[A],tot;
struct Tree{
	int l,r,val,tag;
}tree[4*A];

inline void pushup(int p){
	tree[p].val=tree[lch].val+tree[rch].val;
	return;
}

inline void pushdown(int p){
	if(tree[p].l!=tree[p].r&&tree[p].tag!=0){
		tree[lch].val+=tree[p].tag*(tree[lch].r-tree[lch].l+1);
		tree[rch].val+=tree[p].tag*(tree[rch].r-tree[rch].l+1);
		tree[lch].tag+=tree[p].tag;
		tree[rch].tag+=tree[p].tag;
		tree[p].tag=0;
	}
	return;
}

inline void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r;
	if(l==r){
		tree[p].val=tree[p].tag=0;
		return;
	}
	int mid=(l+r)>>1;
	build(lch,l,mid),build(rch,mid+1,r);
	pushup(p);
	return;
}

inline void add(int p,int l,int r,int val){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].val+=val*(tree[p].r-tree[p].l+1);
		tree[p].tag+=val;
		return;
	}
	pushdown(p);
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid)	add(lch,l,r,val); 
	if(r>-mid+1)	add(rch,l,r,val);
	pushup(p);
	return;
}

inline int qurey(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r)	return tree[p].val;
	pushdown(p);
	int ans=0;
	int mid=(tree[p].l+tree[p].r)>>1;
	if(l<=mid)	ans+=qurey(lch,l,r);
	if(r>=mid+1)	ans+=qurey(rch,l,r);
	return ans;
}

inline void DFS1(int fa,int x){
	f[x]=fa,dep[x]=dep[fa]+1,size[x]=1;
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(z==fa)	continue;
		DFS1(x,z);
		size[x]+=size[z];
		if(size[z]>size[son[x]])	son[x]=z;
	}
	return;
}

inline void DFS2(int x){
	pos[x]=++tot,idx[pos[x]]=x;
	if(son[x]){
		top[son[x]]=top[x];
		DFS2(son[x]);
	}
	for(int y=head[x];y;y=road[y].nex){
		int z=road[y].to;
		if(top[z])	continue;
		top[z]=z;
		DFS2(z);
	}
	return;
}

inline void tree_cut(){
	DFS1(0,1);
	top[1]=1;
	DFS2(1);
	return;
}

inline void road_add(int x,int y,int val){
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])	swap(x,y);
		add(1,pos[top[x]],pos[x],val);
		x=f[top[x]];
	}
	if(dep[x]>dep[y])	swap(x,y);
	add(1,pos[x],pos[y],val);
	return;
}

inline int tree_qurey(int x){
	return qurey(1,pos[x],pos[x]+size[x]-1);
}

signed main(){
	n=in;
	for(int i=1;i<n;i++){
		int u=in,v=in;
		u++,v++;
		ljb(u,v),ljb(v,u);
	}
	tree_cut();
	build(1,1,n);
	q=in;
	while(q--){
		char x=getchar();
		while(x!='A'&&x!='Q')	x=getchar();
		if(x=='A'){
			int u=in,v=in,w=in;
			u++,v++;
			road_add(u,v,w);
		}
		else{
			int u=in;
			u++;
			printf("%lld\n",tree_qurey(u));
		}
	}
	return 0;
}
2020/5/8 21:12
加载中...