# 树链剖分。
## 快把我脑袋都要剖开了。
这是一个省选知识的模板。但是NOIP2016年还是考了天天爱跑步这种省选难度的题。
~~但我不知道为啥还是有人会AK~~
这个算法呢，就是首先**深搜**两遍
第一遍深搜是为了**建树**，记录父亲节点fa、子树的重量size、深度dep、还有重儿子hson。
这里提一下重儿子的概念，就是你这个节点有很多子树，其中某个子树的重量(就是该子树的节点数)最大，我们称他为重儿子。
第二遍深搜是为了**分链**，重新编号id，记录链顶top。
这里如何分链呢，首先你要从根开始将重儿子找出来，然后重儿子的重儿子找出来，然后...，然后找出重儿子的重儿子的重儿子的...的重儿子，将其结成一个链，然后根节点就是该链的链顶。
然后将根节点不是重儿子的儿子作为根节点，重复上两行的操作。
这样树链剖分就完成了。
然后怎么查询&&修改呢。
首先对于链的修改，我们对于一条链(u,v)（其中u的深度比v深即v在u上方，并且每次操作要确保u在v的上方）
如果u,v的top不是同一个
证明u,v不在同一条链上
我们先对深度深的u那条链修改(top[u],u)
然后u重新定义为top[u]的父亲节点，再判断top[u]，top[v]的深度
然后继续修改u的那条链
直到top[u]==top[v]
这时我们对(v,u)进行修改即可。
然后询问也是差不多的，这样1,2种操作就处理完了。
然后3,4操作更简单。
我们回顾深搜第二遍，我们发现某个节点的子树的所有编号都是按照顺序来的。
所以我们直接对(id[x],id[x]+size[x]-1)进行修改或询问即可。
最后要注意的就是快读，无向边，%数，还有long long，就没有什么好说的了。
如果你线段树还有问题，请左转 P3372 【模板】线段树1
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
struct edge{
long long to,next;
}e[200010];
long long n,m,root,mode,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;
char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9'){
sum=sum*10+ch-'0';
ch=getchar();
}
return sum;
}
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]%mode;
}
long long mid=(l+r)>>1,ans=0;
pushdown(rt,mid-l+1,r-mid);
if (mid>=left) ans=(ans+query(l,mid,rt<<1,left,right))%mode;
if (mid+1<=right) ans=(ans+query(mid+1,r,rt<<1|1,left,right))%mode;
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 chain_add(){//1操作
long long u=v_in(),v=v_in(),w=v_in();
long long tu=top[u],tv=top[v];
while (tu!=tv){
if (dep[tu]<dep[tv]){
swap(tu,tv);
swap(u,v);
}
update(1,n,1,id[tu],id[u],w);
u=fa[tu];
tu=top[u];
}
if (dep[u]<dep[v]) swap(u,v);
update(1,n,1,id[v],id[u],w);
}
void chain_query(){//2操作
long long u=v_in(),v=v_in();
long long tu=top[u],tv=top[v],ans=0;
while (tu!=tv){
if (dep[tu]<dep[tv]){
swap(tu,tv);
swap(u,v);
}
ans=(ans+query(1,n,1,id[tu],id[u]))%mode;
u=fa[tu];
tu=top[u];
}
if (dep[u]<dep[v]) swap(u,v);
ans=(ans+query(1,n,1,id[v],id[u]))%mode;
printf("%lld\n",ans);
}
void tree_add(){//3操作
long long x=v_in(),w=v_in();
update(1,n,1,id[x],id[x]+size[x]-1,w);
}
void tree_query(){//4操作
long long x=v_in();
printf("%lld\n",query(1,n,1,id[x],id[x]+size[x]-1)%mode);
}
int main(){
n=v_in();
m=v_in();
root=v_in();
mode=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[root]=1;
dfs1(root,0);
dfs2(root,root);
build(1,n,1);
for (long long i=1;i<=m;i++){
long long q=v_in();
if (q==1) chain_add();
else if (q==2) chain_query();
else if (q==3) tree_add();
else tree_query();
}
return 0;
}
```