长链剖分
简介
长链剖分属于树链剖分的一种,可以把维护子树中只与深度有关的信息做到线性时间。
一般的树链剖分是指剖分轻重链,其依据子节点的个数进行剖分,可以使得我们可以在任意一个点向上跳跃不超过 log 次就能到达根节点,从而可以高效维护两点之间的链的信息。
而长链剖分则是依据子树的深度进行剖分,深度最大的作为重儿子,这样原树就可以被分成若干条互不重复的链,并且保证了重链尽量长。因此长链剖分可以维护树中和深度有关的信息。
实现方式
在长链剖分中,我们常用如下几个数组:
par[x] : x 在树中的父亲。
deep[x]:x 在树中的深度。
len[x]:x 为根的子树最大深度。
son[x]:x 的重儿子,即u->son[u]为重边。
top[x]:x 所在重路径的顶部节点(深度最小)。
这些数组可以通过一次 dfs 来更新。通过定义可知,如果 top[x] = x,那么 x 就是一条长(重)链的起点,此时 len[x] 就是该链的长度(节点数目)。
更新代码可以这样来写:
void dfs(int x){
for(int i = head[x];i ;i = nex[i]){
dfs(ver[i]); if(len[son[x]] < len[ver[i]]) son[x] = ver[i]; } len[x] = len[son[x]]+1; for(int i = head[x];i ;i = nex[i]){
//也可以不更新top数组,在此直接压入q1 if(ver[i] == son[x]) top[son[x]] = top[x]; else top[ver[i]] = ver[i]; } }
讯享网
上述代码是基于邻接表存储‘单向边构成的有根树’,如果是无根树则需加个标记位来防止重复访问。
长链剖分的性质
性质一: 所有的链的长度之和是 O(N)级别
证明:所有点在且仅在一条长(重)链之中,永远只会被计算一次,所以总长度与 N 成正比
性质二: 从任意一个点向上跳跃的次数最多 N \sqrt N N 次。
证明:按照定义,节点 y 的父亲 x 所在的重链的长度一定是不小于 y 所在的重链的,我们知道所有重链的长度之和是 O(N)级别,所以最坏情况就是 1+2+3+…+ n \sqrt n n
,所以最多跳 N \sqrt N N次
例题应用
BAPC2019 A.Appeal to the Audience
题意简述
给定一棵有 k 个叶子节点的二叉树,所有非叶子节点的值等于其左右儿子的最大值,现在给定 k 个整数,求把它们分配在 k 个叶子上,使得整颗树的总权值最大(总权值 = 除根节点外所有节点的权值和)
解题思路
要想使得总和最大,就要使最大值被计算的次数最多。要想某个数被计算的多,就要使得它经过尽量多的节点。于是我们的目标就是找到 k 条从长到短的链,这些链互不重合,且一端是叶子节点。
可以通过长链剖分来将这棵树分为 k 条互不相交的长链,然后按照长度分配元素(长度越大,分配给它的元素值越大)。
代码示例
讯享网#include<bits/stdc++.h> using namespace std; const int N = 1e5+10; const int M = N<<1; typedef long long ll; /* 邻接表代码 */ int head[N],nex[M],ver[M],tot = 1; void addEdge(int x,int y){
ver[++tot] = y; nex[tot] = head[x]; head[x] = tot; } /* 快读代码 */ int getInt(){
int res = 0; bool neg = false; char c = getchar(); while(c != '-' && (c > '9' || c < '0')) c = getchar(); if(c == '-') neg = true, c = getchar(); while(c >= '0' && c <= '9') res = res*10+c-'0',c = getchar(); return neg?-res:res; } int len[N],son[N],top[N]; //依次为当前子树最大深度、重儿子编号、当前链顶节点编号 void dfs(int x){
for(int i = head[x];i;i = nex[i]){
dfs(ver[i]); if(len[son[x]] < len[ver[i]]) son[x] = ver[i]; } len[x] = len[son[x]]+1; for(int i = head[x];i ;i = nex[i]){
//也可以不更新top数组,在此直接压入q1 if(ver[i] == son[x]) top[son[x]] = top[x]; else top[ver[i]] = ver[i]; } } int n,k,a[N]; ll ans = 0; priority_queue<ll> q1,q2; void solve(){
top[1] = 1; dfs(1); for(int i = 2;i <= n;i++) if(top[i] == i) q1.push(len[i]); q1.push(len[1]-1); while(q1.size()){
ans += 1ll * q1.top() * q2.top(); q1.pop(); q2.pop(); } printf("%lld\n",ans); } int main(){
n = getInt(); k = getInt(); for(int i = 1,x;i <= k;i++) x = getInt(),q2.push(x); for(int i = 2,y;i <= n;i++) y = getInt(), addEdge(y+1,i); solve(); return 0; }
Dominant Indices
测试地址
题意简述
给定一颗编号为 1~n 的有根树,根节点编号为 1 。设 d x , i d_{x,i} dx,i 表示以 x 为根的子树中,距 x 为 i 的节点的数目。求出对于每个节点 x,使 d x , i d_{x,i} dx,i 最大的 i ,若有多种可能,则输出最小的 i。
解题思路
这道题刚开始以为就是 dfs,但是 dfs 中转移的时间太高了。看题解是用指针数组(* f[N])来实现 O(1) 时间复杂度内转移的,其效率是由指针的赋值很快保证的,其正确性是由 f[x] = f[son[x] ] + 1 来保证的,即
不过虽然转移的效率很高,但是回溯的过程中还需要合并,如果我们对每个子树都暴力合并的话,时间复杂度还是很高(主要是因为我们每次只能利用指针 O(1) 转移一次,所以要选最长的转移才最划算),所以我们可以用长链剖分,先将当前子树 x 所有的值合并到 x 所在在重链(长链)上,这样每次合并的次数等于短链的长度,然后只要通过 O(1) 转移长链即可。这样等同于每个点都合并了一次,所以总的时间复杂度为 O(N) 。
代码示例
#include<bits/stdc++.h> using namespace std; const int N = 1e6+10; const int M = N<<1; int head[N],ver[M],nex[M],tot = 1; void addEdge(int x,int y){
ver[++tot] = y; nex[tot] = head[x]; head[x] = tot; } int getInt(){
bool neg = false; int res = 0; char c = getchar(); while(c != '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') neg = true, c = getchar(); while(c >= '0' && c <= '9') res = res*10 + c-'0',c = getchar(); return neg?-res:res; } int n,len[N],son[N]; void dfs(int x,int fa){
for(int i = head[x]; i;i = nex[i]){
if(ver[i] == fa) continue; dfs(ver[i],x); if(len[son[x]] < len[ver[i]]) son[x] = ver[i]; } len[x] = len[son[x]] + 1; } int ans[N],*f[N],tmp[N],*idx = tmp; //f 数组是指针数组,可以利用偏移量实现 O(1) 转移,而 idx 代表当前在 tmp 数组的起点 void DP(int x,int fa){
f[x][0] = 1; if(son[x]) f[son[x]] = f[x]+1, DP(son[x],x), ans[x] = ans[son[x]]+1; for(int i = head[x];i ;i = nex[i]){
int y = ver[i]; if(y == fa || y == son[x]) continue; f[y] = idx; idx += len[y]; DP(y,x); for(int j = 1;j <= len[y];j++){
f[x][j] += f[y][j-1]; if((j < ans[x] && f[x][j] >= f[x][ans[x]]) || (j > ans[x] && f[x][j] > f[x][ans[x]])) ans[x] = j; //这里的判断句要保证取f[x][ans[x]]是最大值,且ans[x]尽量小 } } if(f[x][ans[x]] == 1) ans[x] = 0; } int main(){
n = getInt(); for(int i = 1,x,y;i < n;i++){
x = getInt(); y = getInt(); addEdge(x,y); addEdge(y,x); } dfs(1,0); f[1] = idx; idx += len[1]; DP(1,0); for(int i = 1;i <= n;i++) printf("%d\n",ans[i]); return 0; }
参考资料
- 租酥雨的博客
- yyb的博客

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76518.html