树链剖分
先讲解一下一些基础定义(都是在树上)
- 重儿子: 一个节点中所有儿子中子树大小最大的一个儿子(每个节点最多有一个重儿子)
- 轻儿子: 一个节点除重儿子外所有的节点
- 重链: 若干个重儿子组成的链
- 链顶: 一条链中深度最小的节点
以下图为例子 (红色连续线段为重链)
对于节点 1 1 1 来说, 子树大小最大的儿子是 2 2 2 , 2 2 2 最大的是 5 5 5 , 5 5 5的所有儿子子树大小一样大, 随机选一个即可
对于节点 3 3 3 来说, 虽然本身是一个轻儿子, 但是它有重儿子 4 4 4 , 所以也能构成一条重链
由此观之, 所有的点都在某条重链上(重链可能是一个点)
现在, 我们可以通过 d f s dfs dfs 求出以任意节点为根的子树大小, 并且通过全部比较找出每个节点的重儿子.
之后再次 d f s dfs dfs , 把重儿子连成一条又一条链, 记录每个节点所在链的链顶, 等会 L C A LCA LCA 要用
//知道原理就自己写吧, 我的码风一言难尽, 学长写了50行, 我写了270行, 删完之后还剩150行
void dfs(int now,int father){for(int x=0;x<g[now].size();x++){node to=g[now][x];if(to.v==father){continue;}fa[to.v]=now;dfs(to.v,now);siz[now]+=siz[to.v];}return;
}void dfss(int now,int father){int num=0,maxn=-1;for(int x=0;x<g[now].size();x++){node to=g[now][x];if(to.v==father){continue;}if(maxn<siz[to.v]){maxn=siz[to.v];num=to.v;}}for(int x=0;x<g[now].size();x++){node to=g[now][x];if(to.v==father){continue;}if(to.v==num){chain_top[to.v]=chain_top[now];}else{chain_top[to.v]=to.v;}}for(int x=0;x<g[now].size();x++){if(g[now][x].v==father){continue;}dfss(g[now][x].v,now);}return;
}
现在树剖完了, 就该 L C A LCA LCA 了
树链剖分LCA
有两个节点 A , B A,B A,B ,求它们最近公共祖先
L C A LCA LCA 的大致思想就是不断地往上跳, 直到两个节点到根的路径成包含关系时停止. 但是这个往上跳的过程很费时间, 于是我们可以通过某些判断, 让节点往上跳一条重链的长度(如图)
这棵树是挺大的
假设现在我要求 L C A ( 15 , 19 ) LCA(15,19) LCA(15,19) 以下是具体操作步骤
- 判断当前两个节点的链顶是不是同一个点
- 若是, 则输出两个点中深度小的那个
- 若不是, 就让链顶深度最大的那个点往上跳, 跳到链顶的父亲节点
- 重复上述过程, 直到判断为是
要是没太明白的话就自己手动模拟以下:
int LCA(int a,int b){while(ct[a]!=ct[b]){if(dep[chain_top[a]]>=dep[chain_top[b]]){a=fa[chain_top[a]];}else{b=fa[chain_top[b]];}}if(dep[a]<dep[b]){return a;}else{return b;}
}
个人认为这个比倍增 L C A LCA LCA 好理解
例题
今天晚上更