长链剖分学习笔记

,

长链剖分

构造方法：类似于轻重链剖分，把子树最大深度最大的儿子作为重儿子。

性质

  • 一个节点到它所在的长链的链底部的路径，为从这个节点到它子树每个子树所有节点的路径中，最长的一条。
  • 一个节点到根的路径，最多经过 $O(\sqrt n )$ 的链
  • 任意节点 $u$ 的第 $k$ 级祖先 $v$ 所在链的长度一定大于 $k$。
  • 所有链长之和是 $O(n)$ 的。

树上 k 级祖先

找到一个 $i$，满足 $2^i\le k< 2^{i+1}$ ，把 $x$ 向上跳 $2^i$ 级。设还剩下 $k’=k-2^i$

因为 $k-2^i=k’<2^i$ ，而 $x$ 所在链的长度大于等于 $2^i$ ，所以只需要预处理出每条链的长度 $len$，链的顶端向下的 $len$ 个儿子，向上的 $len$ 个祖先。就可以做到 $O(1)$ 查询了。

当时需要 $O(n\log n)$ 预处理出倍增数组。所以总的复杂度是 $O(n\log n)+O(q)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
#define maxn 500005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
#define ui unsigned int
ui s;
inline ui get(ui x) {
	x ^= x << 13;
	x ^= x >> 17;
	x ^= x << 5;
	return s = x; 
}
int n,q;
int h[maxn],head=1;
struct yyy{
	int to,z;
	inline void add(int x,int y) {
		to=y;z=h[x];h[x]=head;
	}
}a[maxn*2];
vector<int>ff[maxn],fs[maxn];
int fa[maxn][21],top[maxn],deep[maxn],lg[maxn],hh[maxn],son[maxn],maxdeep[maxn];
inline void dfs(int x,int pre) {
	int i;deep[x]=deep[pre]+1;fa[x][0]=pre;
	for (i=1;i<=lg[deep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	for (i=h[x];i;i=a[i].z) {
		dfs(a[i].to,x);
		if (maxdeep[x]<maxdeep[a[i].to]+1) {
	    	maxdeep[x]=maxdeep[a[i].to]+1;
	    	son[x]=a[i].to;
		}
	}
}
inline void dfs2(int x,int pre,int v) {
	int i;top[x]=v;
	if (x^v) fs[v].push_back(x);
	if (!son[x]) return ;
	dfs2(son[x],x,v);
	for (i=h[x];i;i=a[i].z) 
		if (a[i].to^son[x]){
			dfs2(a[i].to,x,a[i].to);
			int j,now=x;
		    for (j=1;j<=maxdeep[a[i].to];j++) 
		        if (!now) break;
		        else ff[a[i].to].push_back(now),now=fa[now][0];
		}
}
signed main(void){
//	freopen("1.in","r",stdin);
    int i,j,now,x,k,root;
    ll ans=0,lasans=0;
    read(n);read(q);scanf("%u",&s);
    for (i=1;i<=n;i++) {
    	read(x);
    	if (!x) root=i;
    	else a[++head].add(x,i);
	}
	for (i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for (h[0]=0,i=1;i<=n;i++) hh[i]=1<<lg[i];
	dfs(root,0);
	dfs2(root,0,root);
    for (i=1;i<=q;i++) {
    	x=((get(s)^lasans)%n)+1;k=(get(s)^lasans)%deep[x];
    	if (k==0) {lasans=x;ans^=(i*lasans);continue;}
    	x=fa[x][lg[k]];k=k-hh[k]+deep[top[x]]-deep[x];int now=top[x];
    	if (k==0) lasans=now;
    	else if (k<0) lasans=fs[now][-k-1];
    	else lasans=ff[now][k-1];
    	ans^=(i*lasans);
	}
	printf("%lld\n",ans);
	return 0;
}

长链剖分优化 dp

一般来说，满足 $dp$ 的状态与深度有关，可以考虑用长链剖分优化 $dp$。

具体来说，每次继承重儿子的状态，对于每个非重儿子，一定是一个链的顶端，暴力合并。

继承的复杂度是 $O(1)$ ，所有的非重儿子，复杂度是 $O(\sum len_i)=O(n)$ ，$len_i$ 是第 $i$ 条链的长度。

CF1009F