一，树链剖分

思路： 把树上问题转化到线段树上维护，树上转为序列

1，重链剖分

意义：重链剖分可以将树上的任意一条路径划分成不超过$O(logn)$条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 LCA 为链的一个端点）（一种求lca的新方法！！）

• 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一；如果没有子节点，就无重子节点。

• 定义 轻子节点 表示剩余的所有子结点。

• 从这个结点到重子节点的边为 重边。

• 到其他轻子节点的边为 轻边。

• 若干条首尾衔接的重边构成 重链。

• 把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

维护对象： 线段树或者树状数组等高级数据结构

剖分过程

int son[M],fa[M],size[M],dep[M];
int top[M],dfn[M];int dfs_tree(int x,int f,int depth)（预处理树上的一些数据，深度啦，最大子节等等）
{siz[x]=1;fa[x]=f;dep[x]=depth;int smax=0;for(int i=h[x];~i;i=nxt[i]){int v=to[i];if(v!=f){int ss=dfs_tree(v,x,depth+1);size[x]+=ss;if(ss>smax)son[x]=v;}}
}
void dfs_line(int x,int topx)
{dfn[x]=++cnt;top[x]=topx;for(int i=h[x];~i;i=nxt[i]){int v=to[i];if(!dfn[v]){if(son[x]!=v)dfs_line(v,topx);			else dfs_line(v,v);}}	
}

索引过程

• 这里线段树的midfy和query就不写了
• 注意连续跳链的操作写法，（直觉上是递归，其实是循环）

void  modify_path(int u,int v,ll d)
{while (top[u]!=top[v]){if(dep[top[u]]<dep[top[v] ] )swap(u,v);modify(1,id[top[u]],id[u],d);u=f[top[u]];}if(dep[u]<dep[v])swap(u,v);modify(1,id[v],id[u],d);
}ll query_path(int u,int v)
{ll res= 0;while (top[u]!=top[v]){if(dep[top[u]]<dep[top[v] ] )swap(u,v);res+= query(1,id[top[u] ],id[u]);u=f[top[u]];}if(dep[u]<dep[v])swap(u,v);res= (res+query(1,id[v],id[u]) )%mod;return res;
}void modify_tree(int x, ll d)
{modify(1,id[x], id[x]+ sz[x]-1,d);
}ll query_tree(int x)
{return query(1,id[x],id[x]+sz[x]-1);
}

板子：（小清新写法）

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N= 2e5+9;
struct node {int l,r;ll sum,add;#define sum(p) tr[p].sum#define add(p) tr[p].add#define l(p)   tr[p].l#define r(p)   tr[p].r
}tr[N*4];int h[N], e[N*2], nxt[N*2], idx;
int cnt,n,m;
ll wn[N],a[N],mod;
int top[N],dep[N],sz[N];
int son[N],id[N],f[N];void addx(int a, int b) 
{e[idx] = b, nxt[idx] = h[a], h[a] = idx ++ ;
}template<typename T>inline void read(T &x)
{x=0; bool f=1;char ch = getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch = getchar();}while(ch>='0'&&ch <='9'){x=(x<<1)+(x<<3)+ch-'0'; ch = getchar();}if(!f)x*=-1;
}void wri(ll x)
{if(x<0)putchar('-'),x=-x;if(x>9)wri(x/10);putchar (x%10+'0');
}void pushup(int p)
{sum(p)= sum(p<<1)+ sum(p<<1|1);
}void pushdown(int p)
{sum(p<<1)+= (r(p<<1)- l(p<<1) +1)*add(p)%mod;sum(p<<1|1)+= (r(p<<1|1)- l(p<<1|1) +1)*add(p)%mod;add(p<<1)+= add(p);add(p<<1|1)+= add(p);add(p)= 0;
}void build(int p,int l, int r)
{tr[p]={l,r};if(l==r){tr[p] = {l,r,wn[l], 0};return;}int mid = l+r >>1;build(p<<1,l,mid);build (p<<1|1,mid+1,r);pushup(p);
}void modify(int p,int l,int r,ll d)
{int lx= l(p);int rr= r(p);if(lx>=l&&rr<=r){sum(p)+= (r(p)- l(p)+1)*d%mod;add(p)+= d;return;}pushdown(p);int mid= (lx+rr)>>1;if(l<=mid)modify(p<<1,l,r,d);if(r>mid)modify(p<<1|1,l,r,d);pushup(p);
}ll query(int p,int l,int r)
{int lx= l(p);int rr= r(p);if(lx>=l&&rr<=r)return sum(p);pushdown(p);ll ans= 0;int mid= (lx+rr)>>1;if(l<=mid)ans+= query(p<<1,l,r);if(r>mid)ans+= query(p<<1|1,l,r);return ans;
}void dfs1(int p,int depth,int fa)
{sz[p]=1; dep[p] =depth; f[p]=fa;for(int i=h[p];~i;i=nxt[i]){int j= e[i];if(j== fa)continue;dfs1(j,depth+1,p);if(sz[j]>sz[son[p]])son[p]=j;sz[p]+= sz[j];}
}void dfs2(int p,int t,int fa)
{id[p]=++cnt; wn[cnt]=a[p] ; top[p]=t;if(!son[p])return;dfs2(son[p],t,p);for(int i=h[p];~i;i=nxt[i]){int j= e[i];if(j==son[p] || j==fa)continue;dfs2(j,j,p);}
}void  modify_path(int u,int v,ll d)
{while (top[u]!=top[v]){if(dep[top[u]]<dep[top[v] ] )swap(u,v);modify(1,id[top[u]],id[u],d);u=f[top[u]];}if(dep[u]<dep[v])swap(u,v);modify(1,id[v],id[u],d);
}ll query_path(int u,int v)
{ll res= 0;while (top[u]!=top[v]){if(dep[top[u]]<dep[top[v] ] )swap(u,v);res+= query(1,id[top[u] ],id[u]);u=f[top[u]];}if(dep[u]<dep[v])swap(u,v);res= (res+query(1,id[v],id[u]) )%mod;return res;
}void modify_tree(int x, ll d)
{modify(1,id[x], id[x]+ sz[x]-1,d);
}ll query_tree(int x)
{return query(1,id[x],id[x]+sz[x]-1);
}int main()
{memset(h,-1,sizeof h);ll z;int root=1 ;read(n);   read(m); read(root); read(mod);int x,y,op;for (int i = 1; i <= n; i ++ )read(a[i]);for(int i=2;i<=n;i++)read(x), read(y), addx(x,y), addx(y,x);dfs1(root,1,-1);dfs2(root,root,-1);build(1,1,n);for(int i= 1 ;i<=m;i++){read(op);if(op==1) read(x), read(y) , read(z), modify_path(x,y,z);else  if(op==2)  read(x), read(y) , wri(query_path(x,y)%mod), puts("");else if(op==3) read(x), read(z), modify_tree(x,z);else  read(x),  wri(query_tree(x)%mod), puts("");}return 0;
}

树剖应用

1，边权转点

https://www.luogu.com.cn/blog/user17952/solution-p3038

对于每条边，我们将其深度更大的端点加权，则区间 [l, r] 的加权（或询问）即为去掉深度最小的点，给其余点加权（或询问）。

这么一听处理起来似乎很麻烦，但我们可以思考下树剖查询的过程：

• 1）最后一次树剖查询时，当前两点 x,y 必定在同一重链上（y 的深度小于 x）

• 2）根据处理前的 dfs 序，我们是优先遍历重儿子，那么重儿子在线段树中的编号一定紧邻其父节点（即为其父节点编号 + 1），则我们要忽略深度最小的那个点 y ，即为处理区间 [ y 在线段树中的编号 + 1， x 在线段树中的编号]（另外还要注意的是，y = x 时在线段树内执行会出错，我们要特判这种情况）

3，注意事项：

1，dfs2中如果没有儿子直接return

2，注意边权转点权不算lca，左端点+1

3，注意空间

4，pushdown位置不要忘

5，注意新加入的点权初始化的时候是要转化到序列里的，dfs2和build，以及modify注意起来