P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego 题解

发表于 更新于 分类于 本文字数： 429 阅读时长 ≈ 1 分钟

true
Związek Harcerstwa Bajtockiego
ONTAK2015
提高+ /省选-
#3498db
  • Luogu P8025
  • BZOJ #4281

这道题的题意已经很简洁了，我们就不需要解释了。

对于每一次操作，我们可以分为两种情况：能到达与不能到达。

能到达的直接跳到对应的点即可，不能到达的就直接模拟直接跳就可以了。

因为数据范围是 $10^6$ 级别的，我们尝试优化复杂度。

首先我们可以使用树剖来求出来两个节点的LCA，这样我们就可以快速判断两者之间的距离。

对于跳不到的情况我们还可以继续往下分为三种情况：跳不到LCA，刚好跳到LCA和跳过了LCA。

对于第一种情况，我们直接跳重链直到跳不动重链为止，然后利用重链上DFS序连续的性质直接输出结束节点编号；
对于第二种情况直接输出LCA；
对于第三种情况，我们从目标节点开始向上跳 $dis(x,y)-t$ 步即可，而具体的实现与第一种情况无异。

至此，我们就完美解决了所有问题。

总复杂度为 $O(n \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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000010, M = N << 1;
int n, m;
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dep[N], fa[N], sz[N], son[N];
int id[N], nw[N], top[N], cnt;
void dfs1(int p, int father, int depth)
{
    dep[p] = depth, fa[p] = father, sz[p] = 1;
    for (int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == father)continue;
        dfs1(j, p, depth + 1);
        sz[p] += sz[j];
        if (sz[j] > sz[son[p]])son[p] = j;
    }
}
void dfs2(int p, int t)
{
    id[p] = ++cnt, nw[cnt] = p, top[p] = t;
    if (!son[p])return;
    dfs2(son[p], t);
    for (int i = h[p]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa[p] || j == son[p])continue;
        dfs2(j, j);
    }
}
int lca(int p, int q)
{
    while (top[p] != top[q])
    {
        if (dep[top[p]] < dep[top[q]])swap(p, q);
        p = fa[top[p]];
    }
    if (dep[p] < dep[q])swap(p, q);
    return q;
}
int jump(int p, int k)
{
    while (dep[p] - dep[top[p]] + 1 <= k)
    {//当可以跳完整条重链
        k -= dep[p] - dep[top[p]] + 1;
        p = fa[top[p]];
    }
    return nw[id[p] - k];
}
int main()
{
    memset(h, -1, sizeof(h));
    int u;
    scanf("%d%d%d", &n, &u, &m);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    dfs1(1, 0, 1);
    dfs2(1, 1);
    while (m--)
    {
        int v, step;
        scanf("%d%d", &v, &step);
        int x = lca(u, v);
        int dis1 = dep[u] - dep[x], dis2 = dep[v] - dep[x];
        if (step >= dis1 + dis2)
        {//能跳到
            u = v;
            printf("%d ", u);
        }
        else if (step == dis1)
        {//只能跳到LCA
            u = x;
            printf("%d ", u);
        }
        else if (step < dis1)
        {//连LCA都跳不到
            u = jump(u, step);
            printf("%d ", u);
        }
        else
        {//能跳过LCA
            u = jump(v, dis2 - (step - dis1));
            printf("%d ", u);
        }
    }
    return 0;
}