树链剖分
最有理由学了但不打的东西
树链剖分（重链剖分）就是把一棵树分割成若干条链的形式，可以将树上的任意一条路径划分成不超过\log n条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）。
定义重子节点表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。定义轻子节点表示剩余的所有子结点。从这个结点到重子节点的边为重边。到其他轻子节点的边为轻边。若干条首尾衔接的重边构成重链。把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。
——oi.wiki
那树链剖分可以做什么呢，由“树链剖分可以将树上的任意一条路径划分成不超过\log n条连续的链”，容易想到可以用树链剖分求LCA。具体操作与倍增法类似，但常数要小很多。
例题P3379 【模板】最近公共祖先（LCA）
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read();
int n,m,s,fa[500010],son[500010],siz[500010],dep[500010],top[500010];
vector<int>a[500010];
void dfs1(int x,int p){
fa[x]=p;
siz[x]=1;
dep[x]=dep[p]+1;
for(int i=0;i<a[x].size();i++){
if(a[x][i]==p)continue;
dfs1(a[x][i],x);
siz[x]+=siz[a[x][i]];
if(siz[a[x][i]]>siz[son[x]]){
son[x]=a[x][i];
}
}
}
void dfs2(int x,int t){
top[x]=t;
if(son[x])dfs2(son[x],t);
for(int i=0;i<a[x].size();i++){
if(a[x][i]!=fa[x]&&a[x][i]!=son[x])dfs2(a[x][i],a[x][i]);
}
}
int LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
u=fa[top[u]];
}
else{
v=fa[top[v]];
}
}
if(dep[u]<dep[v])return u;
return v;
}
signed main(){
cin>>n>>m>>s;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs1(s,0);
dfs2(s,s);
while(m--){
int u,v;
cin>>u>>v;
cout<<LCA(u,v)<<endl;
}
return 0;
}
树链剖分结合线段树可以高效地维护树上信息，记录每个节点dfs序，使重子节点优先遍历，这样同一条重链上的节点在dfs序上就是连续的，（同一子树上的节点也是连续的），于是使用线段树就可以高效维护路径和子树上的信息。
7-52行：线段树
53-74行：剖分
75-110行：修改/查询
111-150行：应付输入/输出
例题P3384 【模板】重链剖分/树链剖分
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,r,p,w[100010],fa[100010],son[100010],siz[100010],dep[100010],top[100010],dfn[100010],rnk[100010],cnt;
vector<int>a[100010];
int tree[400000],tag[400000];
void pushup(int p){
tree[p]=tree[p<<1]+tree[p<<1|1];
}
void pushdown(int p,int l,int r){
int d=tag[p];
int mid=(l+r)>>1;
tree[p<<1]+=d*(mid-l+1);
tree[p<<1|1]+=d*(r-mid);
tag[p<<1]+=d;
tag[p<<1|1]+=d;
tag[p]=0;
}
void build(int p,int pl,int pr){
tag[p]=0;
if(pl==pr){
tree[p]=w[rnk[pl]];
return;
}
int mid=(pl+pr)/2;
build(p<<1,pl,mid);
build(p<<1|1,mid+1,pr);
pushup(p);
}
void undate(int l,int r,int d,int p,int pl,int pr){
if(pl>=l&&pr<=r){
tree[p]+=d*(pr-pl+1);
tag[p]+=d;
return;
}
pushdown(p,pl,pr);
int mid=(pl+pr)>>1;
if(l<=mid)undate(l,r,d,p<<1,pl,mid);
if(r>=mid+1)undate(l,r,d,p<<1|1,mid+1,pr);
pushup(p);
}
int query(int l,int r,int p,int pl,int pr){
if(l<=pl&&pr<=r){
return tree[p];
}
pushdown(p,pl,pr);
int mid=(pl+pr)>>1;
int res=0;
if(l<=mid)res+=query(l,r,p<<1,pl,mid);
if(r>=mid+1)res+=query(l,r,p<<1|1,mid+1,pr);
return res;
}
void dfs1(int x,int p){
fa[x]=p;
siz[x]=1;
dep[x]=dep[p]+1;
for(int i=0;i<a[x].size();i++){
if(a[x][i]==p)continue;
dfs1(a[x][i],x);
siz[x]+=siz[a[x][i]];
if(siz[a[x][i]]>siz[son[x]]){
son[x]=a[x][i];
}
}
}
void dfs2(int x,int t){
dfn[x]=++cnt;
rnk[dfn[x]]=x;
top[x]=t;
if(son[x])dfs2(son[x],t);
for(int i=0;i<a[x].size();i++){
if(a[x][i]!=fa[x]&&a[x][i]!=son[x])dfs2(a[x][i],a[x][i]);
}
}
void undate_path(int u,int v,int d){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
undate(dfn[top[u]],dfn[u],d,1,1,n);
u=fa[top[u]];
}
else{
undate(dfn[top[v]],dfn[v],d,1,1,n);
v=fa[top[v]];
}
}
if(dep[u]<dep[v])undate(dfn[u],dfn[v],d,1,1,n);
else undate(dfn[v],dfn[u],d,1,1,n);
}
int query_path(int u,int v){int f=0;if(u==923)f=1;
int res=0;
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]){
res+=query(dfn[top[u]],dfn[u],1,1,n);
u=fa[top[u]];
}
else{
res+=query(dfn[top[v]],dfn[v],1,1,n);
v=fa[top[v]];
}
}
if(dep[u]<dep[v])res+=query(dfn[u],dfn[v],1,1,n);
else res+=query(dfn[v],dfn[u],1,1,n);
return res;
}
void undate_tree(int u,int d){
undate(dfn[u],dfn[u]+siz[u]-1,d,1,1,n);
}
int query_tree(int u){
return query(dfn[u],dfn[u]+siz[u]-1,1,1,n);
}
signed main(){
cin>>n>>m>>r>>p;
for(int i=1;i<=n;i++){
cin>>w[i];
}
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs1(r,0);
dfs2(r,r);
build(1,1,n);
while(m--){
int o;
cin>>o;
if(o==1){
int u,v,d;
cin>>u>>v>>d;
undate_path(u,v,d);
}
if(o==2){
int u,v;
cin>>u>>v;
cout<<query_path(u,v)%p<<endl;
}
if(o==3){
int u,d;
cin>>u>>d;
undate_tree(u,d);
}
if(o==4){
int u;
cin>>u;
cout<<query_tree(u)%p<<endl;
}
}
return 0;
}