【题目来源】
https://www.acwing.com/problem/content/2570/
【题目描述】
给定一棵树，树中包含 n 个节点（编号 1∼n），其中第 i 个节点的权值为 ai。
初始时，1 号节点为树的根节点。
现在要对该树进行 m 次操作，操作分为以下 4 种类型：
● 1 u v k，修改路径上节点权值，将节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值增加 k。
● 2 u k，修改子树上节点权值，将以节点 u 为根的子树上的所有节点的权值增加 k。
● 3 u v，询问路径，询问节点 u 和节点 v 之间路径上的所有节点（包括这两个节点）的权值和。
● 4 u，询问子树，询问以节点 u 为根的子树上的所有节点的权值和。
【输入格式】
第一行包含一个整数 n，表示节点个数。
第二行包含 n 个整数，其中第 i 个整数表示 ai。
接下来 n−1 行，每行包含两个整数 x,y，表示节点 x 和节点 y 之间存在一条边。
再一行包含一个整数 m，表示操作次数。
接下来 m 行，每行包含一个操作，格式如题目所述。
【输出格式】
对于每个操作 3 和操作 4，输出一行一个整数表示答案。
【数据范围】
1≤n,m≤10^5,
0≤ai,k≤10^5,
1≤u,v,x,y≤n
【输入样例】
5
1 3 7 4 5
1 3
1 4
1 5
2 3
5
1 3 4 3
3 5 4
1 3 5 10
2 3 5
4 1
【输出样例】
16
69
【算法分析】
● 树链剖分
（1）树链剖分的核心思想，就是将树中任意一条路径拆分成 段的连续区间（或重链）。拆分后，树的所有操作都可转化为区间操作，且通常采用线段树进行维护。
（2）树链剖分的几个概念
重儿子/轻儿子：结点个数最多的子树的根结点称为当前结点的重儿子，其他子结点称为当前结点的轻儿子。若当前结点存在多个结点个数相同的子树，则任选一个子树的根结点作为当前结点的重儿子。故易知每个结点的重儿子是唯一的。
重边/轻边：重儿子与父结点之间的边，称为重边。其他边称为轻边。
重链：重边构成的极大路径，称为重链。
DFS序：深度优先遍历树的重儿子，可保证树中各条重链结点的编号是连续的。此性质保证了树链剖分后各区间是连续的。
（3）将一条路径拆分为重链的过程，类似于求最近公共祖先（LCA）。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int maxm=maxn<<1;
int val[maxn],e[maxm],ne[maxm],h[maxn],idx;
//id[]:dfn sequence number of the node
//nv[]:point weight of each dfs sequence number
int id[maxn],nv[maxn],tot;
//cnt[]:number of child nodes, top[]:vertex of heavy chain
//son[]:heavy son, fa[]:parent node
int dep[maxn],cnt[maxn],top[maxn],fa[maxn],son[maxn];
int n,m;
struct SegmentTree {
int le,ri;
LL sum,lazy;
} tr[maxn<<2];
void add(int a,int b) {
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int father,int depth) { //dfs1:pretreatment
dep[u]=depth,fa[u]=father,cnt[u]=1;
for(int i=h[u]; i!=-1; i=ne[i]) {
int j=e[i];
if(j==father) continue;
dfs1(j,u,depth+1);
cnt[u]+=cnt[j];
if(cnt[son[u]]<cnt[j]) son[u]=j; //heavy son
}
}
void dfs2(int u,int vx) { //dfs2:split, t:vertex of heavy chain
id[u]=++tot,nv[tot]=val[u],top[u]=vx;
if(!son[u]) return; //leaf node
dfs2(son[u], vx); //Heavy son's heavy chain split
for(int i=h[u]; i!=-1; i=ne[i]) { //handle light son
int j=e[i];
if(j==fa[u] || j==son[u]) continue;
dfs2(j,j); //The vertex of the light son's heavy chain is himself
}
}
/*------------ Content of segment tree ------------*/
void pushup(int u) {
tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u) {
auto &rt=tr[u], &L=tr[u<<1], &R=tr[u<<1|1];
if(rt.lazy) {
L.sum+=rt.lazy*(L.ri-L.le+1);
L.lazy+=rt.lazy;
R.sum+=rt.lazy*(R.ri-R.le+1);
R.lazy+=rt.lazy;
rt.lazy=0;
}
}
void build(int u,int le,int ri) {
tr[u]= {le,ri,nv[ri],0};
if(le==ri) return;
int mid=le+ri>>1;
build(u<<1,le,mid), build(u<<1|1,mid+1,ri);
pushup(u);
}
void update(int u,int le,int ri,int k) {
if(le<=tr[u].le && ri>=tr[u].ri) {
tr[u].lazy+=k;
tr[u].sum+=k*(tr[u].ri-tr[u].le+1);
return;
}
pushdown(u);
int mid=tr[u].le+tr[u].ri>>1;
if(le<=mid) update(u<<1,le,ri,k);
if(ri>mid) update(u<<1|1,le,ri,k);
pushup(u);
}
LL query(int u,int le,int ri) {
if(le<=tr[u].le && ri>=tr[u].ri) return tr[u].sum;
pushdown(u);
int mid=(tr[u].le+tr[u].ri)>>1;
LL res=0;
if(le<=mid) res+=query(u<<1,le,ri);
if(ri>mid) res+=query(u<<1|1,le,ri);
return res;
}
void update_path(int u,int v,int k) {
while(top[u]!=top[v]) { //Climb up to find the same heavy chain
if(dep[top[u]]<dep[top[v]]) swap(u,v);
//Because of dfs order, the id of the upper node
//must be smaller than that of the lower node
update(1,id[top[u]],id[u],k);
u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
//In the same heavy chain, the remaining intervals are processed
update(1,id[v],id[u],k);
}
LL query_path(int u,int v) {
LL res=0;
while(top[u]!=top[v]) { //Climb up to find the same heavy chain
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=query(1,id[top[u]],id[u]);
u=fa[top[u]];
}
if(dep[u]<dep[v]) swap(u,v);
//In the same heavy chain, the remaining intervals are processed
res+=query(1,id[v],id[u]);
return res;
}
void update_tree(int u,int k) { //Add k to all the subtrees
//Because of the order of dfs, the interval can be found directly
//by the number of subtree nodes
update(1,id[u],id[u]+cnt[u]-1,k);
}
LL query_tree(int u) {
//Because of the order of dfs, the interval can be found directly
//by the number of subtree nodes
return query(1,id[u],id[u]+cnt[u]-1);
}
int main() {
scanf("%d",&n);
memset(h,-1,sizeof h);
for(int i=1; i<=n; i++) scanf("%d",&val[i]);
for(int i=1; i<n; i++) {
int a,b;
scanf("%d %d",&a,&b);
add(a,b),add(b,a);
}
dfs1(1,-1,1);
dfs2(1,1);
build(1,1,n);
scanf("%d",&m);
while(m--) {
int op,u,v,k;
scanf("%d%d",&op,&u);
if(op==1) {
scanf("%d%d",&v,&k);
update_path(u,v,k);
} else if(op==2) {
scanf("%d",&k);
update_tree(u,k);
} else if(op==3) {
scanf("%d",&v);
printf("%lld\n",query_path(u,v));
} else printf("%lld\n",query_tree(u));
}
return 0;
}
/*
in:
5
1 3 7 4 5
1 3
1 4
1 5
2 3
5
1 3 4 3
3 5 4
1 3 5 10
2 3 5
4 1
out:
16
69
*/
【参考文献】
https://www.acwing.com/solution/content/62664/
https://www.acwing.com/problem/content/video/2570/
https://blog.csdn.net/qq_46105170/article/details/125497358
