洛谷P5903 树上k级祖先 长链剖分

长链剖分：

与重链剖分类似，重链剖分的关键字是子树规模，长链剖分的关键字是子树深度。

长链剖分有一些重要性质：

性质一：$x$的$k$级祖先所在的长链长度必然$\ge k$，证明如下：

设$x$的$k$级祖先为$y$

若$x$与$y$在同一条长链上，既然$dis(x,y)==k$，那么长链长度一定$\ge k$

若他们不在一条长链上，如图，$t$为$y$所在的长链的末端

因为$dis(x,y)==k$，即$oy+ox==k$，如果$ox>ot$，那么$x$在的链就会是$y$的重链了，因为$o$总是选择深度深的儿子作为深儿子，因此，一定有$ox\le ot$存在，即$oy+ox\le oy+ot$，即$k\le oy+ot\le len[y]$

性质二：$x$沿长链向上跳至根的跳跃次数最大是$O(\sqrt{n}）$级别的，证明如下：

因为每次跳跃$k$长度后链的长度至少是$\ge k$的，因为每次都是跳至顶，链的长度一定递增（可能取等），但链顶点跳至其他链需要多$1$的跳跃，所以每次的跳跃长度严格递增，考虑跳跃次数最差的情况，跳跃长度依次为$1,2,\mathrm{3....}$，求和$\frac{t(t+1)}{2}\le n$

解这个方程就有最大跳跃次数了。

树上$k$级祖先的应用：

要求$x$的$k$级祖先，先找到满足$2^h\le k\le 2^{h+1}$的$h$，然后跳跃至$x$的$2^h$级祖先$y$，根据性质$1$，此时$len[y]\ge 2^h$，剩余需要跳的步数为$k-2^h\le 2^h$（因为$h$满足$k\le 2^{h+1}$），得到$k-2^h\le len[y]$，又因为$k-2^h\ge 0$，所以至少是$y$往上跳，最差情况下最高跳至$top[y]$的$len[y]$级祖先，那么只需要维护每根链顶点$p$的$[1,len[p]]$祖先和儿子，就可以$O(1)$查询了

#include
#define ll long long
#define ui unsigned int
using namespace std;

ui s;
inline ui get(ui x) 
{
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return s = x; 
}

struct way
{
    int to,next;
}edge[1000005];
int cnt,head[500005];

void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int n,q,root,depth[500005],top[500005],len[500005];
int max1[500005],son[500005],f[500005][21];
vector<vector<int>>upp(500005),downn(500005);

void dfs1(int u)
{
    depth[u]=depth[f[u][0]]+1; max1[u]=1; 
    for(int i=1;i<=20;i++) f[u][i]=f[f[u][i-1]][i-1];
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==f[u][0]) continue;
        dfs1(v);
        if(max1[v]>max1[son[u]]) son[u]=v;
    }
    max1[u]+=max1[son[u]];
}

void dfs2(int u,int topf)
{
    top[u]=topf; len[u]=depth[u]+max1[u]-1-depth[top[u]]+1;
    if(son[u]) dfs2(son[u],topf);
    for(int i=head[u];i;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==f[u][0]||v==son[u]) continue;
        dfs2(v,v);
    }
}

int query(int x,int k)
{
    if(!k) return x;
    int base=(int)(log(k)/log(2));
    x=f[x][base]; k-=1<<base;
    k-=depth[x]-depth[top[x]]; x=top[x];
    if(!k) return x;
    else if(k>0) return upp[x][k-1];
    return downn[x][-k-1];
}

int main()
{
    cin>>n>>q>>s; ll tot=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i][0]);
        if(!f[i][0]) root=i;
        else
        {
            add(i,f[i][0]); 
            add(f[i][0],i);
        }
    }
    dfs1(root); dfs2(root,root);
    for(int i=1;i<=n;i++)
    {
        // printf("max1[%d]=%d\n",i,len[i]);
        if(i!=top[i]) continue;
        for(int j=1,x=f[i][0];j<=len[i];j++,x=f[x][0]) upp[i].push_back(x);
        for(int j=1,x=son[i];j<=len[i];j++,x=son[x]) downn[i].push_back(x);
    }
    for(int i=1;i<=q;i++)
    {
        int x=(get(s)^ans)%n+1,k=(get(s)^ans)%depth[x];
        ans=query(x,k); tot^=i*ans;
    }
    cout<<tot;
    return 0;
}
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97