怕到时候忘了，来写一篇笔记
前置芝士：树的存储与遍历，\(dfs\) 序，线段树。
树链剖分的思想及能解决的问题:
树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。
具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。
树链剖分（树剖/链剖）有多种形式，如 重链剖分，长链剖分 和用于 Link/cut Tree 的剖分（有时被称作“实链剖分”），大多数情况下（没有特别说明时），“树链剖分”都指“重链剖分”。
重链剖分可以将树上的任意一条路径划分成不超过 \(O(\log n)\) 条连续的链，每条链上的点深度互不相同（即是自底向上的一条链，链上所有点的 \(LCA\) 为链的一个端点）。
重链剖分还能保证划分出的每条链上的节点 DFS 序连续，因此可以方便地用一些维护序列的数据结构（如线段树）来维护树上路径的信息。
重链剖分
我们给出一些定义：
定义 重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。
定义：轻子节点表示剩余的所有子结点。
从这个结点到重子节点的边为重边。
到其他轻子节点的边为轻边。
若干条首尾衔接的重边构成重链。
把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。
以上来自Oi-wiki。
树链剖分的实现
以洛谷的模板题为例。
先给出以下定义：
\(fa[u]\) 表示\(u\)节点的父节点。
\(dep[u]\) 表示\(u\)节点的深度。
\(top[u]\) 表示\(u\)节点所在链的顶端。
\(son[u]\) 表示\(u\)节点的重儿子\(v\)的编号。
\(siz[u]\) 表示以\(u\)为根的子树的大小。
\(id[u]\) 表示\(u\)在树链剖分的\(dfs\)序。
树剖的实现过程分为：
\(dfs1:\)
\(dfs1\)中我们要处理出\(fa,dep,siz,son\)数组。
代码实现如下：
void dfs1(int u, int fath) //处理fa,dep,siz,son
{
fa[u] = fath;
dep[u] = dep[fath] + 1;
siz[u] = 1;
for(auto v:e[u])
{
if(v == fath) continue;
dfs1(v, u);
siz[u] += siz[v];
if(siz[v] > siz[son[u]])
son[u] = v;
}
}
\(dfs2:\)
\(dfs2\)中我们遵循优先走重边的原则，处理出我们的\(dfs\)序，也就是处理出\(top,id\)数组。
代码实现如下：
void dfs2(int u, int fst) //处理top,id,fst表示当前链的顶端
{
id[u] = ++ idx;
a[idx] = w[u]; //a数组表示节点u的权值在线段树中的位置权值
top[u] = fst;
if(!son[u]) return; //没有重儿子意味着没有子节点
dfs2(son[u], fst); //跟重儿子一条链
for(auto v:e[u])
{
if(v == fa[u] || v == son[u]) continue; //轻儿子既不是父节点也不是重儿子
dfs2(v, v); //以自己为链顶重新开一条链
}
}
树剖求解\(LCA\)（最近公共祖先）：
思路：不断的将两个节点中所在链的链顶深度深的节点往上跳，知道两个节点所在链相同，即\(top[u] == top[v]\)，此时两个节点中深度较低的节点即为\(LCA\)。
代码如下：
int lca(int u, int v)
{
while(top[u] != top[v])
{
if(dep[top[u]] < dep[top[v]]) swap(u, v);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
return u;
}
操作一：将树从 \(x\) 到结点 \(y\) 最短路径上所有节点的值都加上\(z\)
这个时候就要祭出我们的线段树了，在\(dfs2\)中我们采取了优先走重儿子的原则，所以在一条链中的\(dfs\)序一定是连续的，我们能够根据这一特点快速的在线段树中修改某一段的权值。
思路与求解\(LCA\)基本相同，代码：
void trlist_update(int u, int v, int k)
{
while(top[u] != top[v])
{
if(dep[top[u]] <= dep[top[v]]) swap(u, v);
update(id[top[u]], id[u], k, 1, n, 1);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
update(id[u], id[v], k, 1, n, 1);
}
操作二：求树从 \(x\) 到 \(y\) 结点最短路径上所有节点的值之和
理解了\(LCA\)和树上修改权值后，查询其实也不难了，只要将操作一中的修改操作改为查询操作即可，代码如下：
int trlist_query(int u, int v)
{
int res = 0;
while(top[u] != top[v])
{
if(dep[top[u]] <= dep[top[v]]) swap(u, v);
res += query(id[top[u]], id[u], 1, n, 1);
u = fa[top[u]];
}
if(dep[u] > dep[v]) swap(u, v);
res += query(id[u], id[v], 1, n, 1);
return res;
}
操作三：将以 \(x\) 为根节点的子树内所有节点值都加上 \(z\)
因为我们在对树进行剖分的过程中使用的是 \(dfs\) ，所以每一颗子树内的 \(dfs\) 序也是连续的，利用我们之前处理出来的 \(siz\) 数组就能轻松解决这个问题。
代码如下：
void son_update(int u, int k)
{
update(id[u], id[u] + siz[u] - 1, k, 1, n, 1);
}
操作四：求以 \(x\) 为根节点的子树内所有节点值之和
跟操作三基本一样，这里不多赘述，直接放代码：
int son_query(int u)
{
return query(id[u], id[u] + siz[u] - 1, 1, n, 1);
}
完整代码
因为笔者很懒就直接放以前的AC代码了，码风稍有不同，加上了\(long long\)和取模等题目要求。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,r,p,op,idx,cnt;
int head[N],dep[N],top[N],son[N],siz[N],fa[N],w[N],a[N],id[N];
struct edge
{
int to,next;
}e[N<<1];
struct segment_tree
{
int l,r,val,laz_tag;
}t[N<<2];
inline void push_up(int x)
{
t[x].val=(t[x<<1].val+t[x<<1|1].val)%p;
}
inline void push_down(int x)
{
if(!t[x].laz_tag) return;
t[x<<1].laz_tag+=t[x].laz_tag;
t[x<<1|1].laz_tag+=t[x].laz_tag;
t[x<<1].val+=(t[x<<1].r-t[x<<1].l+1)*t[x].laz_tag;
t[x<<1].val%=p;
t[x<<1|1].val+=(t[x<<1|1].r-t[x<<1|1].l+1)*t[x].laz_tag;
t[x<<1|1].val%=p;
t[x].laz_tag=0;
}
inline void build(int l,int r,int x)
{
t[x].l=l;
t[x].r=r;
if(l==r)
{
t[x].val=a[l]%p;
return;
}
int mid=l+r>>1;
build(l,mid,x<<1);
build(mid+1,r,x<<1|1);
push_up(x);
}
inline void update(int nl,int nr,int k,int l,int r,int x)
{
if(nl<=l&&r<=nr)
{
t[x].val+=(r-l+1)*k;
t[x].laz_tag+=k;
return;
}
push_down(x);
int mid=l+r>>1;
if(nl<=mid) update(nl,nr,k,l,mid,x<<1);
if(nr>mid) update(nl,nr,k,mid+1,r,x<<1|1);
push_up(x);
}
inline int query(int nl,int nr,int l,int r,int x)
{
if(nl<=l&&r<=nr)
{
return t[x].val;
}
push_down(x);
int mid=l+r>>1,res=0;
if(nl<=mid) res+=query(nl,nr,l,mid,x<<1);
if(nr>mid) res+=query(nl,nr,mid+1,r,x<<1|1);
return res;
}
inline void add_edge(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void dfs1(int u,int fath)
{
dep[u]=dep[fath]+1;
fa[u]=fath;
siz[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fath) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
inline void dfs2(int u,int fst)
{
id[u]=++idx;
a[idx]=w[u];
top[u]=fst;
if(!son[u]) return;
dfs2(son[u],fst);
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline void trlist_update(int u,int v,int w)
{
w%=p;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
update(id[top[u]],id[u],w,1,n,1);
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
update(id[u],id[v],w,1,n,1);
}
inline int trlist_query(int u,int v)
{
int res=0;
while(top[u]!=top[v])
{
if(dep[top[u]]<dep[top[v]]) swap(u,v);
res+=query(id[top[u]],id[u],1,n,1);
res%=p;
u=fa[top[u]];
}
if(dep[u]>dep[v]) swap(u,v);
res+=query(id[u],id[v],1,n,1);
res%=p;
return res;
}
inline void son_update(int u,int w)
{
update(id[u],id[u]+siz[u]-1,w,1,n,1);
}
inline int son_query(int u)
{
return query(id[u],id[u]+siz[u]-1,1,n,1)%p;
}
signed main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
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;
add_edge(u,v);
add_edge(v,u);
}
dfs1(r,0);
dfs2(r,r);
build(1,n,1);
while(m--)
{
cin>>op;
if(op==1)
{
int u,v,w;
cin>>u>>v>>w;
trlist_update(u,v,w);
}
if(op==2)
{
int u,v;
cin>>u>>v;
cout<<trlist_query(u,v)<<'\n';
}
if(op==3)
{
int u,w;
cin>>u>>w;
son_update(u,w);
}
if(op==4)
{
int u;
cin>>u;
cout<<son_query(u)<<'\n';
}
}
return 0;
}
到这里就能很轻松的解决树上修改等一系列问题了，接下来给出几道例题。
\(1\).P3038 [USACO11DEC]Grass Planting G（思考如何边权转点权）
\(2\). P4427 [BJOI2018]求和（预处理+树剖）
\(3\). P1505 [国家集训队]旅游（很裸的树剖，不懂为什么评紫，注意节点编号是从\(0\)开始的即可）
标签：剖分,int,top,笔记,树链,dep,节点,son,id From： https://www.cnblogs.com/syz1552672065/p/17080811.html