Blog of RuSun

\begin {array}{c} \mathfrak {One Problem Is Difficult} \\\\ \mathfrak {Because You Don't Know} \\\\ \mathfrak {Why It Is Diffucult} \end {array}

树上 k 级祖先

发表于 分类于
本文字数： 4k 阅读时长 ≈ 4 分钟
标签：        

求树上 $k$ 级祖先。

重链剖分做，只要 $k$ 还可以跳到链顶，就跳到链顶，否则直接找到对应 $dfn$ 序的前面 $k$ 。复杂度 $O(n) / O(\log n)$ 。

查看代码 
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
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10, M = N << 1;
int n, q, d[N], p[N], sz[N];
int stmp, dfn[N], rnk[N], top[N], son[N];
int idx, hd[N], nxt[M], edg[M];
void dfs1(int x)
{
    sz[x] = 1;
    son[x] = -1;
    for (int i = hd[x]; ~i; i = nxt[i])
        if (!d[edg[i]])
        {
            d[edg[i]] = d[x] + 1;
            p[edg[i]] = x;
            dfs1(edg[i]);
            sz[x] += sz[edg[i]];
            if (son[x] == -1 || sz[edg[i]] > sz[son[x]])
                son[x] = edg[i];
        }
}
void dfs2(int x, int t)
{
    dfn[x] = ++stmp;
    rnk[stmp] = x;
    top[x] = t;
    if (~son[x])
        dfs2(son[x], t);
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != son[x] && edg[i] != p[x])
            dfs2(edg[i], edg[i]);
}
int query(int x, int k)
{
    while (k >= d[x] - d[top[x]])
    {
        k -= d[x] - d[top[x]];
        x = top[x];
        if (k)
        {
            k--;
            x = p[x];
        }
        else
            return x;
    }
    return rnk[dfn[x] - k];
}
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    d[1] = 1;
    dfs1(1);
    dfs2(1, 1);
    for (int x, k; q; q--)
    {
        scanf("%d%d", &x, &k);
        printf("%d\n", query(x, k));
    }
    return 0;
}

长链剖分，复杂度 $O(n \log n) / O(1)$ 。

查看代码 
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
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10, M = N, K = 20;
vector<int> w[N], v[N];
int n, q, lg[N], d[N], fa[N][K];
int dis[N], son[N], top[N];
int idx, hd[N], nxt[M], edg[M];
void dfs1(int x)
{
    son[x] = -1;
    for (int i = hd[x]; ~i; i = nxt[i])
    {
        fa[edg[i]][0] = x;
        dis[edg[i]] = d[edg[i]] = d[x] + 1;
        for (int k = 1; (1 << k) < d[edg[i]]; k++)
            fa[edg[i]][k] = fa[fa[edg[i]][k - 1]][k - 1];
        dfs1(edg[i]);
        dis[x] = max(dis[x], dis[edg[i]]);
        if (son[x] == -1 || dis[edg[i]] > dis[son[x]])
            son[x] = edg[i];
    }
}
void dfs2(int x, int t)
{
    top[x] = t;
    if (x == t)
    {
        for (int i = d[x], u = x; i <= dis[x]; i++, u = fa[u][0])
            w[x].push_back(u);
        for (int i = d[x], u = x; i <= dis[x]; i++, u = son[u])
            v[x].push_back(u);
    }
    if (~son[x])
        dfs2(son[x], t);
    for (int i = hd[x]; ~i; i = nxt[i])
        if (edg[i] != son[x])
            dfs2(edg[i], edg[i]);
}
int query(int x, int k)
{
    if (!k)
        return x;
    x = fa[x][lg[k]], k -= 1 << lg[k];
    k -= d[x] - d[top[x]], x = top[x];
    return k >= 0 ? w[x][k] : v[x][-k];
}
void add(int a, int b)
{
    nxt[++idx] = hd[a];
    hd[a] = idx;
    edg[idx] = b;
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        hd[i] = -1;
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i >> 1] + 1;
    for (int i = 1, u, v; i < n; i++)
    {
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    d[1] = 1;
    dfs1(1);
    dfs2(1, 1);
    for (int x, k; q; q--)
    {
        scanf("%d%d", &x, &k);
        printf("%d\n", query(x, k));
    }
    return 0;
}
相关文章