长链剖分学习笔记 + [Vijos] lxhgww的奇思妙想 + CF1009F Dominant Indices [长链剖分]

• $定义$定义

与重链剖分的定义相似, 只不过重儿子为链的长度最长的儿子 .

• $性质$性质

1. 任意一个点 $K$K 级祖先所在长链的长度一定大于等于 $K$K .

2. 任意一个点跳重链到根所用的次数不超过 $\sqrt{N}$N ​ .
   $证$证: 每次向上跳, 链的长度都会至少加 $1$1, $1,2,3,\mathrm{4...}\sqrt{N}$1,2,3,4...N ​

• $一个应用$一个应用

$O\left(1\right)求K级祖先:$O(1) 求K级祖先:

链接

对每个 $Top$Top记录以下内容 $\downarrow$↓

• 它 所在长链链长 那么多次 的祖先和重儿子们, 存在 std::vector 里面, 设为 $A\left[\right],B\left[\right]$A[],B[], 复杂度 $O\left(N\right)$O(N) .

• 倍增数组 $Fk[i,j]$Fk[i,j] 表示 $i$i 的第 $2^j$2j 祖先, 复杂度 $O\left(NlogN\right)$O(NlogN) .

• 每个 $i$i 的最高二进制位表示的数字 $max\_pos\left[i\right]$max_pos[i], 复杂度 $O\left(NlogN\right)$O(NlogN) .

现在求 $i$i 的 $K$K 级祖先, 先到达点 $F[i,max\_pos[K\left]\right]$F[i,max_pos[K]], 设为 $y$y,

此时还需要跳 $tmp=K-2^{max\_pos\left[K\right]}$tmp=K−2max_pos[K] 步, 分类讨论

• 若 $dep\left[y\right]-dep\left[Top\right[y\left]\right]\ge tmp$dep[y]−dep[Top[y]]≥tmp 然后直接跳到 $A[i,dep[y]-dep[Top\left[y\right]]-tmp]$A[i,dep[y]−dep[Top[y]]−tmp] 即可.
• 若 $dep\left[y\right]-dep\left[Top\right[y\left]\right]\&lt;tmp$dep[y]−dep[Top[y]]<tmp 然后直接跳到 $B[i,tmp-(dep\left[y\right]-dep\left[Top\right[y\left]\right]\left)\right]$B[i,tmp−(dep[y]−dep[Top[y]])] 即可.

$为什么可以这么做呢?$为什么可以这么做呢?

设 $Top\left[y\right]$Top[y] 所在长链长度为 $len\left[Top\right[y\left]\right]$len[Top[y]], 则 $len\left[Top\right[y\left]\right]\ge 2^{max\_pos\left[K\right]}\ge K-2^{max\_pos\left[K\right]}$len[Top[y]]≥2max_pos[K]≥K−2max_pos[K],
又因为 $Top\left[y\right]$Top[y] 的 $len\left[Top\right[y\left]\right]$len[Top[y]] 级及以下祖先和儿子全部存到了 $A\left[Top\right[y\left]\right],B\left[Top\right[y\left]\right]$A[Top[y]],B[Top[y]] 中, 所以直接调用即可实现 $O\left(1\right)$O(1) .

$代码实现:$代码实现:

#include<bits/stdc++.h>
#define pb push_back
#define reg register

const int maxn = 1000006;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

int N;
int M;
int K;
int num0;
int o_pos;
int last_ans;
int pw[maxn];
int fa[maxn];
int len[maxn];
int son[maxn];
int dep[maxn];
int Top[maxn];
int head[maxn];
int Fk[maxn][21];
int max_pos[maxn];

std::vector <int> A[maxn], B[maxn];

struct Edge{ int nxt, to; } edge[maxn << 1];

void Add(int from, int to){
        edge[++ num0] = (Edge){ head[from], to };
        head[from] = num0;
}

void DFS(int k, int fa){
        len[k] = 1;
        dep[k] = dep[fa] + 1;
        for(reg int i = 1; i <= 19; i ++) Fk[k][i] = Fk[Fk[k][i-1]][i-1];
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(to == fa) continue ;
                Fk[to][0] = k;
                DFS(to, k);
                if(len[to] > len[son[k]]) son[k] = to;
        }
        len[k] = len[son[k]] + 1;
}

void DFS_2(int k, int top){ 
        Top[k] = top;
        if(son[k]) DFS_2(son[k], top);
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(to == Fk[k][0] || to == son[k]) continue ;
                DFS_2(to, to);
        }
}

void Work(){
        o_pos = read() ^ last_ans, K = read() ^ last_ans;
        if(!K){ printf("%d\n", last_ans = o_pos); return ; }
        else if(dep[o_pos] <= K){ printf("%d\n", last_ans = 0); return ; }
        int y = Fk[o_pos][max_pos[K]];
        int tmp = pw[max_pos[K]];
        if(K - tmp <= dep[y]-dep[Top[y]]) last_ans = B[Top[y]][dep[y]-dep[Top[y]]-(K-tmp)];
        else last_ans = A[Top[y]][K-tmp - (dep[y]-dep[Top[y]])];
        printf("%d\n", last_ans);
}

int main(){
        N = read();
        for(reg int i = 1; i < N; i ++){
                int x = read(), y = read();
                Add(x, y), Add(y, x);
        }
        DFS(1, 0); DFS_2(1, 1);
        pw[0] = 1;
        for(reg int i = 1; i <= 19; i ++) pw[i] = pw[i-1] << 1;
        for(reg int i = 1; i <= N; i ++)
                for(reg int j = 19; j >= 0; j --)
                        if(i >= pw[j]){ max_pos[i] = j; break ; }
        for(reg int i = 1; i <= N; i ++){
                if(Top[i] != i) continue ;
                int t = i;
                for(reg int j = 1; j <= len[i]; j ++, t = Fk[t][0]) A[i].pb(t);
                t = i;
                for(reg int j = 1; j <= len[i]; j ++, t = son[t]) B[i].pb(t);
        }
        M = read();
        while(M --) Work();
        return 0;
}

• $相关难点$相关难点

主要是指针部分比较新, 这里说一下怎么操作,
首先有一个数组 $foc\left[\right]$foc[], 其内存空间分为若干段, 分别存储了各个长链的相关信息,
在做有关 $dp$dp 遍历到短儿子(设为 $to$to)时, 在 $foc\left[\right]$foc[] 中开一个以 $to$to为开头的长链长度的空间, 来存储 $to$to 往下长链的信息,
这样做的好处是: 同一长链的节点可以 通过移动指针 $O\left(1\right)$O(1) 更新 $dp$dp 数组 , 进而做到整体 $O\left(N\right)$O(N) 复杂度 .

• $一道例题$一道例题

$DominantIndices$Dominant Indices

给出一棵有根树，对于每个节点 $x$x，定义一个无穷序列 $d$d,
其中 $d(x,i)$d(x,i)表示以 $x$x为根节点的子树中到 $x$x的距离恰好为 $i$i的点的个数， $i=0$i=0~ $无穷$无穷，
现在对每个点 $x$x，希望求出一个东西 $j$j，使得对于任意 $k\&lt;j，d(x,k)\&lt;d(x,j)$k<j，d(x,k)<d(x,j)，对于任意 $k\&gt;j,d(x,k)\le d(x,j)$k>j,d(x,k)≤d(x,j) .

$正解部分$正解部分

$题意:$题意: 对每个点求距离 $Ans\left[i\right]$Ans[i], 使得 $Ans\left[i\right]$Ans[i] 在使得 $d(i,Ans[i\left]\right)$d(i,Ans[i]) 最大的同时 $Ans\left[i\right]$Ans[i] 尽量小 .

设 $F[i,j]$F[i,j] 表示距离 $i$i 节点 $j$j 的节点个数, $F[i,j]={\sum }_{i\in so{n}_i}F[to,j-1]$F[i,j]=i∈soni​∑​F[to,j−1] ,
$初值:$初值: $F[i,0]=1$F[i,0]=1 .

重儿子通过长链直接继承, 轻儿子暴力继承即可, 时间复杂度

$实现部分$实现部分

#include<bits/stdc++.h>
#define reg register

const int maxn = 4e6 + 6;

int N;
int *it;
int num0;
int *F[maxn];
int Ans[maxn];
int foc[maxn];
int son[maxn];
int len[maxn];
int head[maxn];

struct Edge{ int nxt, to; } edge[maxn << 1];

void Add(int from, int to){
        edge[++ num0] = (Edge){ head[from], to };
        head[from] = num0;
}

void DFS(int k, int fa){
        len[k] = 1;
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(to == fa) continue ;
                DFS(to, k);
                if(len[son[k]] < len[to]) son[k] = to;
        }
        len[k] = len[son[k]] + 1;
}

void DFS_2(int k, int fa){
        F[k][0] = 1;
        if(son[k]) F[son[k]] = F[k] + 1, DFS_2(son[k], k), Ans[k] = (F[son[k]][Ans[son[k]]]==1) ? Ans[k] : (Ans[son[k]]+1);
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(to == son[k] || to == fa) continue ;
                F[to] = it, it += len[to];
                DFS_2(to, k);
                for(reg int i = 1; i <= len[to]; i ++){
                        F[k][i] += F[to][i-1];
                        if(F[k][i] > F[k][Ans[k]] || (F[k][i] == F[k][Ans[k]] && Ans[k] > i)) Ans[k] = i;
                }
        }
}

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i < N; i ++){
                int x, y; scanf("%d%d", &x, &y);
                Add(x, y), Add(y, x);
        }
        DFS(1, 0);
        F[1] = it = foc;
        it += len[1];
        DFS_2(1, 0);
        for(reg int i = 1; i <= N; i ++) printf("%d\n", Ans[i]);
        return 0;
}

• $其他例题$其他例题

• Hotel加强版
• AT2268
• AT1998
• AGC009D