一般来说，可以解决的问题是：子树内信息的修改，子树内信息的查询、路径的修改、路径的查询

先是剖分成链，形成序列，然后用处理序列的数据结构处理，也就是线段树

我们所常说的树链剖分其实是轻重链剖分
树链剖分可以处理树上的任意两点间路径和任意一点子树的信息修改与查询(配合线段树这样的数据结构..)

建议先学会线段树和 LCA。

首先注意下文中权值是赋在点上的 而不是在边上
如果遇到权值在边上的情况 把权值赋给这条边连接的两点中深度较大的那个点即可

1.引入

线段树是通过维护一些区间 并且把待处理区间拆分成一定数量个维护的区间
树链剖分思想相似 将树剖分成log⁡n">lognlog?n级别条互相不相交的链 同时保证每一个点都在且仅在一条链上(所有链可以覆盖所有点) 对于每一条路径可以将其拆分成log⁡n">lognlog?n级别条链分别维护链上点权
链就是一些点 这些点首尾相接 除了两端的点只有一个点与之相连 其他的点都有两点与之有边相连
在这里的链中 链维护一些深度递增的点 没有任意两点在树中深度相同
子树的问题在后文提到

2.思想

如果将一条很长的链一起处理 可以优化效率
为了使得链与链不相交 必定有一些边不能在链中 我们把这些边成为轻边 因为这样的边不会很多 遇到时直接处理就行了
于是我们通过一定形式将一棵树分成轻边和链 所有的链都一起处理 而对于轻边则直接一条一条边处理

就是为了把n">nn变成log⁡n">lognlog?n啊

3.实现

1.预处理

我们把链称为重链
首先我们要让重链的取法最优
我们对于每一个点 显然它到它儿子(我们先随便指定一个点当做根)的所有出边中 只有一条边能在重链中 否则链会相交
在这里我们取子树大小最大的儿子作为重儿子 对于任意一个点该点和它的重儿子位于同一条重链上 到其余的儿子的路径作为轻边
这样就会形成一些重链了 如果觉得太抽象可以看看下面的图片

至于为什么取子树大小最大在后面复杂度证明中会提到

首先我们要通过dfs预处理出每一个点的子树大小、父亲节点编号、深度、重儿子编号。
这些都不难处理 在下面的代码中给出注释了

这时候这棵树已经剖分好了 但是为了维护链上信息 我们还要再处理一些信息
首先每一条链可以视为一个区间 我们可以用线段树来维护链信息

因此 我们需要给树上每一个点编号 代表它在线段树中的编号 因为每一条重链在线段树上必须对应一个连续的区间 而原来的顺序未必能满足这个要求
其次再建立一个数组维护线段树上编号为i的点对应原树上的点的编号 在线段树建树时会用到
所以我们要再dfs一遍 而且这个dfs的遍历顺序要稍微调整一下 通过每一次先遍历点的重儿子再遍历其他儿子来保证每一条重链在线段树上必须对应一个连续的区间

等等 还没结束
现在我们是不知道每一条重链对应的区间编号
所以对于每一个点我们还要处理出它所在重链的顶端的点(该链上深度最小的点)编号

如果一个点在重链的中间 那么只用处理这条重链的一部分就行了(该点到顶端的部分) 链上的点对应线段树中编号是随深度递增的
如果路径上的两个点都在同一条重链上 只要处理这两个点之间的部分就行了

如果是求简单的LCA的话，就不需要线段树这样的结构了，因为不涉及到修改，而且也没有rec,rid这样的记录编号的数组。

#include
#include
#include
#include
#include
#include
#include
#include

P3384 【模板】轻重链剖分

#include
#include
#include
#include
#include
#define Rint register int
#define mem(a,b) memset(a,(b),sizeof(a))
#define Temp template
using namespace std;
typedef long long LL;
Temp inline void read(T &x){
    x=0;T w=1,ch=getchar();
    while(!isdigit(ch)&&ch!='-')ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^'0'),ch=getchar();
    x=x*w;
}

#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define len (r-l+1)

const int maxn=200000+10;
int n,m,r,mod;
//见题意 
int e,beg[maxn],nex[maxn],to[maxn],w[maxn],wt[maxn];
//链式前向星数组，w[]、wt[]初始点权数组 
int a[maxn<<2],laz[maxn<<2];
//线段树数组、lazy操作 
int son[maxn],id[maxn],fa[maxn],cnt,dep[maxn],siz[maxn],top[maxn]; 
//son[]重儿子编号,id[]新编号,fa[]父亲节点,cnt dfs_clock/dfs序,dep[]深度,siz[]子树大小,top[]当前链顶端节点 
int res=0;
//查询答案 

inline void add(int x,int y){//链式前向星加边 
    to[++e]=y;
    nex[e]=beg[x];
    beg[x]=e;
}
//-------------------------------------- 以下为线段树 
inline void pushdown(int rt,int lenn){
	laz[rt<<1]+=laz[rt];
	laz[rt<<1|1]+=laz[rt];
    a[rt<<1]+=laz[rt]*(lenn-(lenn>>1));
    a[rt<<1|1]+=laz[rt]*(lenn>>1);
    a[rt<<1]%=mod;
    a[rt<<1|1]%=mod;
    laz[rt]=0;
}

inline void build(int rt,int l,int r){
    if(l==r){
        a[rt]=wt[l];
        if(a[rt]>mod)a[rt]%=mod;
        return;
    }
    build(lson);
    build(rson);
    a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
}

inline void query(int rt,int l,int r,int L,int R){
	if(L<=l&&r<=R){res+=a[rt];res%=mod;return;}
	else{
		if(laz[rt])pushdown(rt,len);
		if(L<=mid)query(lson,L,R);
		if(R>mid)query(rson,L,R);
	}
}

inline void update(int rt,int l,int r,int L,int R,int k){
    if(L<=l&&r<=R){
		laz[rt]+=k;
		a[rt]+=k*len;
	}
	else{
		if(laz[rt])pushdown(rt,len);
		if(L<=mid)update(lson,L,R,k);
		if(R>mid)update(rson,L,R,k);
		a[rt]=(a[rt<<1]+a[rt<<1|1])%mod;
	}
}
//---------------------------------以上为线段树 
inline int qRange(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){//当两个点不在同一条链上 
		if(dep[top[x]]dep[y])swap(x,y);//把x点深度更深的那个点
	res=0;
	query(1,1,n,id[x],id[y]);//这时再加上此时两个点的区间和即可
	ans+=res;
	return ans%mod;
}

inline void updRange(int x,int y,int k){//同上 
	k%=mod;
	while(top[x]!=top[y]){
		if(dep[top[x]]dep[y])swap(x,y);
	update(1,1,n,id[x],id[y],k);
}

inline int qSon(int x){
	res=0;
	query(1,1,n,id[x],id[x]+siz[x]-1);//子树区间右端点为id[x]+siz[x]-1 
	return res;
}

inline void updSon(int x,int k){//同上 
	update(1,1,n,id[x],id[x]+siz[x]-1,k);
}

inline void dfs1(int x,int f,int deep){//x当前节点，f父亲，deep深度 
	dep[x]=deep;//标记每个点的深度 
	fa[x]=f;//标记每个点的父亲 
	siz[x]=1;//标记每个非叶子节点的子树大小 
	int maxson=-1;//记录重儿子的儿子数 
	for(Rint i=beg[x];i;i=nex[i]){
		int y=to[i];
		if(y==f)continue;//若为父亲则continue 
		dfs1(y,x,deep+1);//dfs其儿子 
		siz[x]+=siz[y];//把它的儿子数加到它身上 
		if(siz[y]>maxson)son[x]=y,maxson=siz[y];//标记每个非叶子节点的重儿子编号 
	}
}

inline void dfs2(int x,int topf){//x当前节点，topf当前链的最顶端的节点 
	id[x]=++cnt;//标记每个点的新编号 
	wt[cnt]=w[x];//把每个点的初始值赋到新编号上来 
	top[x]=topf;//这个点所在链的顶端 
	if(!son[x])return;//如果没有儿子则返回 
	dfs2(son[x],topf);//按先处理重儿子，再处理轻儿子的顺序递归处理 
	for(Rint i=beg[x];i;i=nex[i]){
		int y=to[i];
		if(y==fa[x]||y==son[x])continue;
		dfs2(y,y);//对于每一个轻儿子都有一条从它自己开始的链 
	}
}

int main(){
    read(n);read(m);read(r);read(mod);
    for(Rint i=1;i<=n;i++)read(w[i]);
    for(Rint i=1;i


【一本通的题目】
1560：【例 1】树的统计

 给出了每个节点的权值

#include
#include
#include
#include
#include
#include
#include
#include


1561：「HAOI2015」树上操作

 点修改、子树内修改、路径求和---------给了每个节点的权值

#include
using namespace std;
struct SYM{
    int to,next;
}edge[200010];
struct ASJ{
    long long  sum;
    long long lz;
}tree[400010];
int head[100010],tot;
int n,m;
int w[100010],dep[100010],fa[100010],son[100010],siz[100010],top[100010],wet[100010],id[100010];
void addedge(int x,int y){
    edge[++tot].to=y;
    edge[tot].next=head[x];
    head[x]=tot;
}
void build(int i,int l,int r){                          //建树 
    if(l==r){
        tree[i].sum=wet[l]; ///这个是在dfs2里面处理好了，因为调用顺序是dfs1、dfs2、build 
        return ;
    }
    int mid=(l+r)/2;
    build(2*i,l,mid);                                   //左儿子 
    build(2*i+1,mid+1,r);                               //右儿子 
    tree[i].sum=(tree[2*i].sum+tree[2*i+1].sum);
}
void pushdown(int i,long long len){                    //LAZY下传 ---在破环这个区间的时候使用 
    tree[2*i].lz+=tree[i].lz;
    tree[2*i+1].lz+=tree[i].lz;
    tree[2*i].sum+=(tree[i].lz*(len-len/2));
    tree[2*i+1].sum+=(tree[i].lz*(len/2));
    tree[i].lz=0;                                      //别忘了清零 
}
void update(int i,int l,int r,int L,int R,long long k){//更新操作 
    if(l>=L&&r<=R){
        tree[i].sum+=k*(r-l+1);       
        tree[i].lz+=k;
        return ;
    }
    int mid=(l+r)/2;
    pushdown(i,(r-l+1));                               //下传LAZY 
    if(L<=mid) update(2*i,l,mid,L,R,k);
    if(R>mid) update(2*i+1,mid+1,r,L,R,k);
    tree[i].sum=tree[2*i].sum+tree[2*i+1].sum;
}
long long query(int i,int l,int r,int L,int R){//查询操作 
    long long ans=0;
    if(l>=L&&r<=R){
        return tree[i].sum;
    }
    int mid=(l+r)/2;
    pushdown(i,(r-l+1));
    if(L<=mid) ans+=query(2*i,l,mid,L,R);
    if(R>=mid+1) ans+=query(2*i+1,mid+1,r,L,R);
    return ans;
}
//----------------------------------------------------------------上面是线段树 
void dfs1(int now,int from){               //处理dep，fa，siz，以及重儿子son 
    dep[now]=dep[from]+1;
    fa[now]=from;
    int maxson=-1;
    siz[now]=1;
    for(int i=head[now];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==from) continue;
        dfs1(v,now);
        siz[now]+=siz[v];
        if(siz[v]>maxson){
            son[now]=v;
            maxson=siz[v];
        }
    }
}
int cnt;
void dfs2(int now,int topr){              //处理重链链顶top，新点id，新点权值wet 
    id[now]=++cnt;
    top[now]=topr;
    wet[cnt]=w[now];
    if(!son[now]) return;
    dfs2(son[now],topr);                  //先处理重儿子，再处理轻儿子 
    for(int i=head[now];i;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa[now]||v==son[now]) continue;
        dfs2(v,v);                        //每个轻儿子都是一个新的链顶，别忘了换链顶！！！ 
    }
}
void update1(int x,int k){
    update(1,1,n,id[x],id[x]+siz[x]-1,k); //子树是连续的所以左节点id[x]，右节点id[x]+siz[x]-1 
}
long long q1(int x,int y){               //这里我写的有点麻烦，因为一个点固定为根1，所以其实可以省略一些，不过这里的代码是可以应用于每一个树链剖分路经查询的 
    long long ans=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]dep[y]) swap(x,y);
    ans+=query(1,1,n,id[x],id[y]);
    return ans;
}
int main(){
    int no,x,y;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
    for(int i=1;i


1562：「NOI2015」软件包管理器

//依赖关系
//安装一个软件包---》它依赖的会产生影响
//卸载一个包---》依赖它的会产生影响
/*每次安装软件，就把根节点到x软件路径上的值全部变为1  ---路径修改 
同理，每次卸载软件，就把x以及它的子树的值变为0       ----子树修改 
故我们可以用区间和的思想，每次操作之前记录一下tree[root].sum的值，更新之后再查询一遍tree[root].sum的值，两者之差的绝对值则为答案。

#include
#include
#include
#include
#include
#include
#include
#include


1563：染色

 P2486   https://www.luogu.com.cn/problem/P2486
很好的一道树链剖分。树剖后，线段树要记录左端点l,右端点r，左端点的颜色lc,右端点的颜色rc,区间成段更新的标记tag,区间有多少颜色段。
区间合并的时候要注意如果左子树的右端和右子树的左端颜色相同那么数量要减一。
但是存在一个问题当前剖到的链与上一次的链在相交的边缘可能颜色相同，如果颜色相同答案需要减一。
所以统计答案的时候要记录下上一次剖到的链的左端点的颜色，与当前剖到的链右端点的颜色（因为在处理出的线段树中越靠近根的点位置越左）
比较这两个颜色，若相同则答案减
1。又由于有u和v两个位置在向上走，那么要记录ans1，ans2两个变量来存“上一次的左端点颜色”。有一点需要注意，当
top[u]=top[v]的时候，即已经在同一个重链上时，两边端点颜色都要考虑与对应ans比较颜色，相同答案要相应减一。

#include
#include
#include
#include
#include
#include
#include
#include