BZOJ 4034: [HAOI2015]T2

标签（空格分隔）： OI BZOJ 树链剖分线段树

Time Limit: 10 Sec
Memory Limit: 256 MB

Description

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input

第一行包含两个整数 N, M 。表示点数和操作数。

接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to ，表示该树中存在一条边 (fr, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操
作的种类（ 1-3 ），之后接这个操作的参数（ x 或者 x a ）。
Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

Sample Input

5 5

1 2 3 4 5

1 2

1 4

2 3

2 5

3 3

1 2 1

3 5

2 1 2

3 3
Sample Output

HINT

对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不

会超过 10^6 。
Source

鸣谢bhiaibogf提供

Solution####

树链剖分+线段树

Code####

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<vector>
using namespace std;
#define PA pair<int,int>
const int N=0,M=0;
int read()
{int s=0,f=1;char ch=getchar();
 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
 return s*f;
}
//smile please
int n,m;
int val[100005];
int lpos[100005],rpos[100005],up[100005],dfn,siz[100005],fa[100005];
long long sum[1<<18],tag[1<<18];
int be[100005],bn[200005],bv[200005],bw=1;
void put(int u,int v)
{bw++;bn[bw]=be[u];be[u]=bw;bv[bw]=v;}
int ss;
void dfs1(int x)
{
	for(int i=be[x];i;i=bn[i])
	   if(bv[i]!=fa[x])
	     fa[bv[i]]=x,
		 dfs1(bv[i]),
		 siz[x]+=siz[bv[i]];
	siz[x]++;
}
void dfs2(int x,int UP)
{
	int ma=0;
	for(int i=be[x];i;i=bn[i])
	   if(siz[bv[i]]>siz[ma]&&bv[i]!=fa[x])
	     ma=bv[i];
	up[x]=UP;lpos[x]=rpos[x]=++dfn;
	if(!ma)return;
	   dfs2(ma,UP);
	   rpos[x]=max(rpos[x],rpos[ma]);
	for(int i=be[x];i;i=bn[i])
	   {int v=bv[i];if(v==ma||v==fa[x])continue;
	    dfs2(v,v);
	    rpos[x]=max(rpos[x],rpos[v]);
	   }
}
void down(int l,int r,int x)
{
	if(l==r)return;
	long long t=tag[x];tag[x]=0;int mid=l+r>>1;
	tag[x<<1]+=t,sum[x<<1]+=t*(mid-l+1);
	tag[x<<1|1]+=t,sum[x<<1|1]+=t*(r-mid);
}
void add(int x,int l,int r,int L,int R,long long s)
{
	if(L>R)return;
	if(tag[x])down(l,r,x);
	if(l==L&&r==R)
	  {tag[x]+=s;sum[x]+=(r-l+1)*s;return;}
	int mid=l+r>>1;
	add(x<<1,l,mid,L,min(R,mid),s);
	add(x<<1|1,mid+1,r,max(L,mid+1),R,s);
	sum[x]=sum[x<<1]+sum[x<<1|1];
}
long long ask(int x,int l,int r,int L,int R)
{
	if(L>R)return 0;
	if(tag[x])down(l,r,x);
	if(l==L&&r==R)
	  return sum[x];
	int mid=l+r>>1;
	return ask(x<<1,l,mid,L,min(R,mid))+ask(x<<1|1,mid+1,r,max(L,mid+1),R);
}
long long ask1(int x)
{
	long long ans=0;
	for(;x;x=fa[up[x]])
	    ans+=ask(1,1,n,lpos[up[x]],lpos[x]);
	return ans;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	   val[i]=read();
	for(int i=1;i<n;i++)
	   {int f=read(),s=read();
	    put(s,f);
	    put(f,s);
	   }
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=n;i++)
	   add(1,1,n,lpos[i],lpos[i],val[i]);
	while(m--)
	  {int k=read(),x=read();
	   if(k==1)add(1,1,n,lpos[x],lpos[x],read());
	   if(k==2)add(1,1,n,lpos[x],rpos[x],read());
	   if(k==3)printf("%lld
",ask1(x));
	  }
	return 0;
}