BZOJ 2836 魔法树

题目大意

请你维护一棵树，支持：$A \to B$的路径上点的权值加上一个数，查询一个点的子树点权和。

这道题就直接上树链剖分就行了，板子题，注意使用long long。

注意两点：

1. 一定要向上跳！tx=fa[top[tx]]!!!
2. 线段树各函数里千万不能弄混laz和val!!!

#include <cstdio>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
#define maxN 100010
int n,inx,iny,inz,q,siz[maxN],fa[maxN],son[maxN],depth[maxN],num[maxN],top[maxN],cnt;
int to[maxN<<1],nex[maxN<<1],head[maxN],tot;
long long val[maxN<<2],laz[maxN<<2];
char mode[10];
void addedge(int tx,int ty) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;}
void dfs1(int pos,int pre)
{
	depth[pos]=depth[pre]+1;
	fa[pos]=pre;
	siz[pos]=1;
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=pre)
		{
			dfs1(to[i],pos);
			siz[pos]+=siz[to[i]];
			if(siz[son[pos]]<siz[to[i]]) son[pos]=to[i];
		}
	return;
}
void dfs2(int pos,int pre)
{
	num[pos]=++cnt;
	top[pos]=pre;
	if(son[pos]) dfs2(son[pos],pre);
	for(int i=head[pos];i;i=nex[i])
		if(to[i]!=fa[pos]&&to[i]!=son[pos])
			dfs2(to[i],to[i]);
}
void pushdown(int pos,int l,int r)
{
	if(laz[pos])
	{
		int mid=(l+r)>>1;
		laz[lson]+=laz[pos],laz[rson]+=laz[pos];
		val[lson]+=laz[pos]*(mid-l+1),val[rson]+=laz[pos]*(r-mid);
		laz[pos]=0;
	}
}
void pushup(int pos) {val[pos]=val[lson]+val[rson];}
void qadd(int pos,int l,int r,int x,int y,int z)
{
	if(x<=l&&r<=y)
	{
		laz[pos]+=z;
		val[pos]+=1ll*z*(r-l+1);//
		return;
	}
	pushdown(pos,l,r);
	int mid=(l+r)>>1;
	if(x<=mid) qadd(lson,l,mid,x,y,z);
	if(y>mid) qadd(rson,mid+1,r,x,y,z);
	pushup(pos);
	return;
}
void add(int tx,int ty,int tz)
{
	while(top[tx]!=top[ty])
	{
		if(depth[top[tx]]<depth[top[ty]]) swap(tx,ty);
		qadd(1,1,n,num[top[tx]],num[tx],tz);
		tx=fa[top[tx]];//
	}
	if(depth[tx]>depth[ty]) swap(tx,ty);
	qadd(1,1,n,num[tx],num[ty],tz);
}
long long query(int pos,int l,int r,int x,int y)
{
	if(x<=l&&r<=y) return val[pos];
	pushdown(pos,l,r);
	int mid=(l+r)>>1;
	long long ret=0;
	if(x<=mid) ret+=query(lson,l,mid,x,y);
	if(y>mid) ret+=query(rson,mid+1,r,x,y);
	return ret;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;++i) scanf("%d%d",&inx,&iny),++inx,++iny,addedge(inx,iny),addedge(iny,inx);
	dfs1(1,0);
	dfs2(1,1);
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s",mode);
		switch(mode[0])
		{
			case 'A':
			{
				scanf("%d%d%d",&inx,&iny,&inz),++inx,++iny;
				add(inx,iny,inz);
				break;
			}
			case 'Q':
			{
				scanf("%d",&inx),++inx;
				printf("%lld\n",query(1,1,n,num[inx],num[inx]+siz[inx]-1));
				break;
			}
		}
	}
}