一.引入

其实一个合理的引入对学生的兴趣影响很大

$-cqbzgm$

但是竞赛哪里有那么多兴趣 , 更重要的是恒心与毅 力    ( 虽然我没有   但是竞赛哪里有那么多兴趣,更重要的是恒心与毅力_{~~(虽然我没有~~} 但是竞赛哪里有那么多兴趣,更重要的是恒心与毅力  (虽然我没有  ​

二.算法介绍

树链剖分，顾名思义，指一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。

$-源于百度百科$

三.实现

光写个概念是无用的,我们还得去想办法实现.

我们先引入一点东西:

重儿子:一个结点的所有儿子中,子树节点数最多的那个

轻儿子:一个结点除重儿子以外的其他儿子

重链:从一个轻儿子开始,一直往他的重儿子走出的链

轻链:除重链外的其他链

然后看这张图:

我们用黄色来标记重儿子和重链:

再按照优先遍历重链对结点重新编号:

然后你就会发现,我们完成了$dfs$序.

根据以上的流程,我们就可以写$dfs$序了.

代码:

/*
dfs1:找出所有结点之间的关系 并求得每个结点的重儿子
dfs2:对所有结点重新编号
id[u]:dfs序后的编号
tmp[cnt]:序号cnt对应结点u
fa[u]:u的父亲结点
d[u]:u的深度
size[u]:u为根节点的子树的结点个数
son[u]:u的重儿子
top[u]:u所在的重链顶端结点
*/
void dfs1(int u){
	size[u] = 1, d[u] = d[fa[u]] + 1;//这个点本身size=1,深度为他父亲+1
	for(int i = head[u]; i; i = g[i].next){
		int v = g[i].to;
		if(v == fa[u])continue;
		fa[v] = u;
		dfs1(v);
		size[u] += size[v];
		if(size[son[u]] < size[v])son[u] = v;//求重儿子
	}
}
void dfs2(int u, int front){
	top[u] = front, id[u] = ++ cnt, tmp[cnt] = u;
	if(son[u])dfs2(son[u], front);
	for(int i = head[u]; i; i = g[i].next){
		int v = g[i].to;
		if(v != fa[u] && v != son[u])dfs2(v, v);//一个点位于轻链底端,那么他的top必然是它本身
	}
}

然后我们就可以迎接例题了~~(终于写完了 h h h _{hhh} hhh​~~