# 这道题是裸的树链剖分算法
# 这道题是裸的树链剖分算法
# 这道题是裸的树链剖分算法
我觉得还可以。因为我读优忘记写负数了。
然后对于点操作，线段树从自己到自己增加就行了。
然后和 P3384 【模板】树链剖分 一模一样的做法，简直就是双倍经验
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
struct edge{
long long to,next;
}e[200010];
long long n,m,len,tot;
long long a[100010],tree[400010],lazy[400010];
long long head[100010],real[100010],id[100010],fa[100010],hson[100010],dep[100010],size[100010],top[100010];
long long v_in(){//快读
long long sum=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f*=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
sum=sum*10+ch-'0';
ch=getchar();
}
return sum*f;
}
void add(long long u,long long v){//加边
e[++len].to=v;
e[len].next=head[u];
head[u]=len;
}
/*线段树(Segment Tree)*/
void pushup(long long rt){//上推
tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void pushdown(long long rt,long long ln,long long rn){//下推
if (lazy[rt]){
tree[rt<<1]+=lazy[rt]*ln;
tree[rt<<1|1]+=lazy[rt]*rn;
lazy[rt<<1]+=lazy[rt];
lazy[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
}
void build(long long l,long long r,long long rt){//建树
if (l==r){
tree[rt]=a[real[l]];
return;
}
long long mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(long long l,long long r,long long rt,long long left,long long right,long long c){//修改操作
if (l>=left&&r<=right){
tree[rt]+=c*(r-l+1);
lazy[rt]+=c;
return;
}
long long mid=(l+r)>>1;
pushdown(rt,mid-l+1,r-mid);
if (mid>=left) update(l,mid,rt<<1,left,right,c);
if (mid+1<=right) update(mid+1,r,rt<<1|1,left,right,c);
pushup(rt);
}
long long query(long long l,long long r,long long rt,long long left,long long right){//询问操作
if (l>=left&&r<=right) return tree[rt];
long long mid=(l+r)>>1,ans=0;
pushdown(rt,mid-l+1,r-mid);
if (mid>=left) ans+=query(l,mid,rt<<1,left,right);
if (mid+1<=right) ans+=query(mid+1,r,rt<<1|1,left,right);
pushup(rt);
return ans;
}
/*树链剖分*/
void dfs1(long long u,long long f){//第一遍深搜(建树,记录fa,size,dep,hson)
fa[u]=f;
size[u]=1;
for (long long i=head[u];i!=0;i=e[i].next){
long long v=e[i].to;
if (fa[u]!=v){
dep[v]=dep[u]+1;
dfs1(v,u);
if (hson[u]==0||size[hson[u]]<size[v]) hson[u]=v;
size[u]+=size[v];
}
}
}
void dfs2(long long u,long long anc){//第二遍深搜(分链,重新编号,记录top,id,real)
top[u]=anc;
id[u]=++tot;
real[tot]=u;
if (hson[u]==0) return;
dfs2(hson[u],anc);
for (long long i=head[u];i!=0;i=e[i].next){
long long v=e[i].to;
if (v!=fa[u]&&v!=hson[u]) dfs2(v,v);
}
}
void point_add(){//1操作
long long x=v_in(),w=v_in();
update(1,n,1,id[x],id[x],w);
}
void tree_add(){//2操作
long long x=v_in(),w=v_in();
update(1,n,1,id[x],id[x]+size[x]-1,w);
}
void chain_query(){//3操作
long long u=v_in();
long long tu=top[u],ans=0;
while (tu!=1){
ans+=query(1,n,1,id[tu],id[u]);
u=fa[tu];
tu=top[u];
}
ans+=query(1,n,1,id[1],id[u]);
printf("%lld\n",ans);
}
main(){
n=v_in();
m=v_in();
for (long long i=1;i<=n;i++) a[i]=v_in();
for (long long i=1;i<n;i++){
long long u=v_in(),v=v_in();
add(u,v);//无向边
add(v,u);
}
dep[1]=1;
dfs1(1,0);
dfs2(1,1);
build(1,n,1);
for (long long i=1;i<=m;i++){
long long q=v_in();
if (q==1) point_add();
else if (q==2) tree_add();
else chain_query();
}
return 0;
}
```