树链剖分

适用题目特征

修改树上两点之间的路径上/子树中所有点的值。
查询树上两点之间的路径上/子树中节点权值的和/极值/其它（在序列上可以用数据结构维护，便于合并的信息）

原理

一颗子树/链内的dfs序是连续的。所以可以用数据结构维护。

例题

Luogu P3384
代码如下

/*
Luogu P3384
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<"  "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int n,m,root,mod;
struct node{
    int from,to;
}edge[maxn<<1];
int head[maxn],tot=1;
int w[maxn];
void add(int from,int to){
    edge[++tot].from=head[from],head[from]=tot,edge[tot].to=to;
}
int f[maxn],d[maxn],sz[maxn],son[maxn];
int top[maxn],wt[maxn],id[maxn],cnt=0;
void dfs1(int x,int fa,int deep){
    d[x]=deep,sz[x]=1,f[x]=fa;
    int maxs=0;
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==fa) continue;
        dfs1(y,x,deep+1);
        sz[x]+=sz[y];
        if(sz[y]>maxs) {maxs=sz[y],son[x]=y;}
    }
}
void dfs2(int x,int anc){
    id[x]=++cnt,wt[cnt]=w[x],top[x]=anc;
    if(!son[x]) return;
    dfs2(son[x],anc);
    for(int i=head[x];i;i=edge[i].from){
        int y=edge[i].to;
        if(y==f[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}
struct segmentTree{
    int l,r,sum,tag,sz;
}tr[maxn<<2];
void build(int rt,int l,int r){
    tr[rt].l=l,tr[rt].r=r,tr[rt].sz=r-l+1;
    if(l==r){tr[rt].sum=wt[l];return;}
    int mid=l+r>>1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    tr[rt].sum=(tr[rt<<1].sum+tr[rt<<1|1].sum+mod)%mod;
}
void spread(int rt){
    if(tr[rt].tag){
        tr[rt<<1].tag=(tr[rt<<1].tag+tr[rt].tag)%mod;
        tr[rt<<1|1].tag=(tr[rt<<1|1].tag+tr[rt].tag)%mod;
        tr[rt<<1].sum=(tr[rt<<1].sum+tr[rt<<1].sz*tr[rt].tag)%mod;
        tr[rt<<1|1].sum=(tr[rt<<1|1].sum+tr[rt<<1|1].sz*tr[rt].tag)%mod;
        tr[rt].tag=0;
    }
}
void update(int rt,int l,int r,int v){
    if(tr[rt].l>=l&&tr[rt].r<=r){tr[rt].sum=(tr[rt].sum+tr[rt].sz*v)%mod;tr[rt].tag=(tr[rt].tag+v)%mod;return;}
    spread(rt);
    int mid=tr[rt].l+tr[rt].r>>1;
    if(mid>=l) update(rt<<1,l,r,v);
    if(mid<r) update(rt<<1|1,l,r,v);
    tr[rt].sum=(tr[rt<<1].sum+tr[rt<<1|1].sum+mod)%mod;
}
int query(int rt,int l,int r){
    if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].sum%mod;
    spread(rt);
    int mid=tr[rt].l+tr[rt].r>>1;
    int res=0;
    if(mid>=l) res=(res+query(rt<<1,l,r))%mod;
    if(mid<r) res=(res+query(rt<<1|1,l,r))%mod;
    return res;
}
void treeAdd(int x,int y,int v){
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        update(1,id[top[x]],id[x],v);
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    update(1,id[x],id[y],v);
}
int treeSum(int x,int y){
    int res=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        res=(res+query(1,id[top[x]],id[x]))%mod;
        x=f[top[x]];
    }
    if(d[x]>d[y]) swap(x,y);
    res=(res+query(1,id[x],id[y]))%mod;
    return res;
}
void solve(){
    dfs1(root,0,1);
    dfs2(root,root);
    build(1,1,n);
//  rep(i,1,n) D(wt[i]);
//  E; 
    while(m--){
        int op,x,y,z;
        scanf("%d",&op);
        if(op==1){
            scanf("%d%d%d",&x,&y,&z);
            treeAdd(x,y,z%mod); 
        }
        if(op==2){
            scanf("%d%d",&x,&y);
            printf("%d\n",treeSum(x,y));
        }
        if(op==3){
            scanf("%d%d",&x,&z);
            update(1,id[x],id[x]+sz[x]-1,z%mod);
        }
        if(op==4){
            scanf("%d",&x);
            printf("%d\n",query(1,id[x],id[x]+sz[x]-1));
        }
    }
}
int main() {
//  ios::sync_with_stdio(false);
//  freopen("轻重链剖分.in","r",stdin);
    scanf("%d%d%d%d",&n,&m,&root,&mod);
    rep(i,1,n) scanf("%d",&w[i]);
    int from,to;
    rep(i,1,n-1) scanf("%d%d",&from,&to),add(from,to),add(to,from);
    solve();
    return 0;
}
#endif
#ifdef method_2

#endif
#ifdef method_3
/*

*/

#endif