[Luogu 3178] HAOI2013 树上操作

<题目链接>

---

#include <cstdio>

#include <cstring>

const int MAXN=100010,MAXM=200010;

int n,m;

class HLD

{

	public:

		HLD(void)

		{

			num=cnt=0;

			memset(vis,0,sizeof vis);

			memset(head,0,sizeof head);

			memset(p,0,sizeof p);

		}

		void Init(void)

		{

			for(int i=1;i<=n;++i)

				scanf("%lld",&p[i].v);

			for(int i=1,u,v;i<n;++i)

			{

				scanf("%d %d",&u,&v);

				AddEdges(u,v);

			}

			DFS1(1,1),DFS2(1,1),T.Build(this,1,1,n);

		}

		void AddNode(int x,long long k)

		{

			T.Update(p[x].DFN,k);

		}

		void AddSubtree(int x,long long k)

		{

			T.Add(1,p[x].DFN,p[x].DFN+p[x].size-1,k);

		}

		long long SumPath(int x)

		{

			int a;

			long long ans=0LL;

			while(x)

				ans+=T.Sum(1,p[a=p[x].top].DFN,p[x].DFN),x=p[a].ft;

			return ans;

		}

	private:

		bool vis[MAXN];

		int num,cnt,head[MAXN],rank[MAXN];

		struct node

		{

			int d,ft,son,top,size,DFN;

			long long v;

		}p[MAXN];

		struct edge

		{

			int nxt,to;

			edge(int _nxt=0,int _to=0)

			{

				nxt=_nxt,to=_to;

			}

		}e[MAXM];

		class SegmentTree

		{

			public:

				void Build(HLD *qwq,int i,int l,int r)

				{

					s[i]=node(l,r,0LL);

					if(l==r)

					{

						f[l]=i,s[i].v=qwq->p[qwq->rank[l]].v;

						return;

					}

					int j=i<<1,mid=l+r>>1;

					Build(qwq,j,l,mid),Build(qwq,j|1,mid+1,r);

					PushUp(i);

				}

				void Update(int i,long long v)

				{

					i=f[i];

					while(i)

						s[i].v+=v,i>>=1;

				}

				void Add(int i,int l,int r,long long v)

				{

					if(l==s[i].l && r==s[i].r)

					{

						Modify(i,v);

						return;

					}

					if(s[i].l^s[i].r && s[i].lazy)

						PushDown(i);

					int j=i<<1,mid=s[i].l+s[i].r>>1;

					if(r<=mid)

						Add(j,l,r,v);

					else if(l>mid)

						Add(j|1,l,r,v);

					else

						Add(j,l,mid,v),Add(j|1,mid+1,r,v);

					PushUp(i);

				}

				long long Sum(int i,int l,int r)

				{

					if(l==s[i].l && r==s[i].r)

						return s[i].v;

					if(s[i].l^s[i].r && s[i].lazy)

						PushDown(i);

					int j=i<<1,mid=s[i].l+s[i].r>>1;

					if(r<=mid)

						return Sum(j,l,r);

					else if(l>mid)

						return Sum(j|1,l,r);

					else

						return Sum(j,l,mid)+Sum(j|1,mid+1,r);

				}

			private:

				int f[MAXN];

				struct node

				{

					int l,r;

					long long v,lazy;

					node(int _l=0,int _r=0,long long _lazy=0LL)

					{

						l=_l,r=_r,lazy=_lazy;

					}

				}s[MAXN<<2];

				void Modify(int i,long long v)

				{

					s[i].v+=v*(long long)(s[i].r-s[i].l+1);

					s[i].lazy+=v;

				}

				void PushUp(int i)

				{

					int j=i<<1;

					s[i].v=s[j].v+s[j|1].v;

				}

				void PushDown(int i)

				{

					int j=i<<1;

					Modify(j,s[i].lazy),Modify(j|1,s[i].lazy);

					s[i].lazy=0LL;

				}

		}T;

		void AddEdge(int u,int v)

		{

			e[++cnt]=edge(head[u],v);

			head[u]=cnt;

		}

		void AddEdges(int u,int v)

		{

			AddEdge(u,v),AddEdge(v,u);

		}

		void DFS1(int u,int k)

		{

			p[u].d=k,p[u].size=1;

			for(int i=head[u],v;i;i=e[i].nxt)

				if(!p[v=e[i].to].size)

				{

					DFS1(v,k+1);

					p[v].ft=u,p[u].size+=p[v].size;

					if(p[v].size>p[p[u].son].size)

						p[u].son=v;

				}

		}

		void DFS2(int u,int top)

		{

			vis[u]=p[u].top=top,p[u].DFN=++num,rank[num]=u;

			if(p[u].son)

				DFS2(p[u].son,top);

			for(int i=head[u],v;i;i=e[i].nxt)

				if(!vis[v=e[i].to])

					DFS2(v,v);

		}

}HLT;

int main(int argc,char *argv[])

{

	scanf("%d %d",&n,&m);

	HLT.Init();

	for(int i=1,opt,x;i<=m;++i)

	{

		long long k;

		scanf("%d %d",&opt,&x);

		switch(opt)

		{

			case 1:

				scanf("%lld",&k);

				HLT.AddNode(x,k);

				break;

			case 2:

				scanf("%lld",&k);

				HLT.AddSubtree(x,k);

				break;

			case 3:

				printf("%lld\n",HLT.SumPath(x));

				break;

		}

	}

	return 0;

}