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 3Sample Output
6
9
13HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
题目分析：
树链剖分的裸题 因为轻重链的标号是连续的 所以x的子树的最大编号是number[x]+size[x]-1;
然后用线段树维护一下就好了
注意 函数里的c也要开long long 因为极限数据是10^11 爆int
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
struct your
{
int x,y;
long long sum;
long long add;
}a[500000];
int net[200010],head[200010],to[200010];
int val[200010],top[200010],number[200010],v[200010];
int fa[200010],size[200010],son[200010],deep[200010];
int tot,cnt;
void add(int x,int y)
{
net[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
void dfs(int x,int temp)
{
fa[x]=temp;
deep[x]=deep[temp]+1;
size[x]=1;
for(int i=head[x];i;i=net[i])
{
if(to[i]==temp) continue;
dfs(to[i],x);
size[x]+=size[to[i]];
if(size[son[x]]<size[to[i]]) son[x]=to[i];
}
}
void dfs2(int x,int temp)
{
number[x]=++cnt;
top[x]=temp;
val[number[x]]=v[x];
if(son[x]) dfs2(son[x],temp);
for(int i=head[x];i;i=net[i])
if(to[i]!=son[x]&&to[i]!=fa[x])
dfs2(to[i],to[i]);
}
void build(int dx,int dy,int num)
{
a[num].x=dx,a[num].y=dy;
if(dx==dy)
{
a[num].sum=val[dx];
return ;
}
int mid=(dx+dy)>>1;
build(dx,mid,num<<1);
build(mid+1,dy,num<<1|1);
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
void pushdown(int num)
{
a[num<<1].add+=a[num].add;
a[num<<1|1].add+=a[num].add;
a[num<<1].sum+=a[num].add*(a[num<<1].y-a[num<<1].x+1);
a[num<<1|1].sum+=a[num].add*(a[num<<1|1].y-a[num<<1|1].x+1);
a[num].add=0;
}
void update(int dx,int dy,long long c,int num)
{
if(dx==0||dy==0) return ;
if(a[num].x==dx&&a[num].y==dy)
{
a[num].sum+=c*(a[num].y-a[num].x+1);
a[num].add+=c;
return;
}
if(a[num].add) pushdown(num);
int mid=(a[num].x+a[num].y)>>1;
if(dx>mid) update(dx,dy,c,num<<1|1);
else if(dy<=mid) update(dx,dy,c,num<<1);
else
{
update(dx,mid,c,num<<1);
update(mid+1,dy,c,num<<1|1);
}
a[num].sum=a[num<<1].sum+a[num<<1|1].sum;
}
long long asksum(int dx,int dy,int num)
{
if(dx==a[num].x&&a[num].y==dy)
return a[num].sum;
if(a[num].add) pushdown(num);
int mid=(a[num].x+a[num].y)>>1;
if(dy<=mid) return asksum(dx,dy,num<<1);
if(dx>mid) return asksum(dx,dy,num<<1|1);
return asksum(dx,mid,num<<1)+asksum(mid+1,dy,num<<1|1);
}
long long findsum(int x)
{
long long sum=0;
while(top[x]!=1)
{
sum+=asksum(number[top[x]],number[x],1);
x=fa[top[x]];
}
sum+=asksum(1,number[x],1);
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,0);
dfs2(1,1);
build(1,n,1);
for(int i=1;i<=m;i++)
{
int tmp;
scanf("%d",&tmp);
if(tmp==1)
{
int x,c;
scanf("%d%d",&x,&c);
update(number[x],number[x],c,1);
}
else if(tmp==2)
{
int x,c;
scanf("%d%d",&x,&c);
update(number[x],number[x]+size[x]-1,c,1);
}
else
{
int x;
scanf("%d",&x);
printf("%lld\n",findsum(x));
}
}
}
