题解：P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

Ciallo_Error · 2025-11-26 15:42:41 · 题解

P8025 [ONTAK2015] Związek Harcerstwa Bajtockiego

题目大意：

给定一棵树，一开始我们位于 m 点。之后有 k 次询问，每次我们可以走 t 步，沿着唯一路径前往 d 点，能到则到，不能到则尽量走。

知识点：树剖求树上 K 级祖先

默认都会树上 K 级祖先，如果不会请先学习【模板】树上 K 级祖先。

思路：

很板的树上 K 级祖先模板题。

对于每次询问我们先求出到 d 点的路径长度 dist。

lca = LCA(x, d);

dist = h[x] + h[d] - 2 * h[lca];
//h数组是以1为根时，每个节点的深度

然后我们进行分类讨论：

• 可以直接走到 d 点时，我们修改位置到 d。

if (dist <= t) x = d;

• 不能到达 lca 点时，我们修改位置到 x 的 t 级祖先。

if (h[x] - h[lca] >= t) x = query(x, t);
//query求的是树上k级祖先

• 可以到达 lca 点但不能到达 d 点时，相当于求 d 点的 dist - t 级祖先。

if (h[x] - h[lca] < t) x = query(d, dis - t);

代码

//码风一般，见谅qwq
//代码中写的是长链剖分
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10;
int fa[N];
int h[N];
int maxh[N];
int deep[N];
int top[N];
int id[N];
int have[N];
vector<int> l[N];

int n, m, k;
int root;
int tot;

void dfs1(int u, int father, int high){
    fa[u] = father;
    h[u]  = high;
    maxh[u] = high;

    for (auto v : l[u]){
        if (v == fa[u]) continue;

        dfs1(v, u, high + 1);

        maxh[u] = max(maxh[u], maxh[v]);

        if (maxh[v] > maxh[deep[u]]) deep[u] = v;
    }

    return;
}

void dfs2(int u, int Top){
    ++tot;

    top[u] = Top;
    id[u]  = tot;
    have[tot] = u;

    if (deep[u] == 0) return;

    dfs2(deep[u], Top);

    for (auto v : l[u]){
        if (v == fa[u] || v == deep[u])  continue;

        dfs2(v, v);
    }

    return;
}

int LCA(int x, int y){
    while (top[x] != top[y]){
        if (h[top[x]] < h[top[y]]) swap(x, y);

        x = fa[top[x]];
    }

    if (h[y] < h[x]) return y;

    return x;
}

int query(int u, int father){
    while (h[u] - h[top[u]] < father){
        father -= h[u] - h[top[u]];

        father -= 1;

        u = fa[top[u]];
    }

    int v = have[id[u] - father];

    return v;   
}

namespace IO{
    inline int read(){
        int x = 0, f = 1;
        char c = getchar();

        while(c < '0' || c > '9'){
            if (c == '-') f = -1;

            c = getchar();
        }

        while(c >= '0' && c <= '9'){
            x *= 10;
            x += c - '0';

            c = getchar();
        }

        return x * f;
    }

    void write(int x){
        if (x < 0){
            putchar('-');
            x = -x;
        }

        if (x < 10){
            putchar(x + '0');
            return;
        }
        else{
            write(x / 10);

            putchar(x % 10 + '0');

            return;
        }
    }
}

signed main(){
    n = IO::read();
    m = IO::read();
    k = IO::read();

    for (int i = 1; i < n; i++){
        int u, v;
        u = IO::read();
        v = IO::read();

        l[u].push_back(v);
        l[v].push_back(u);
    }

    root = 1;

    dfs1(root, 0, 1);

    dfs2(root, root);

    int x = m;  
    while(k--){
        int d, t;
        d = IO::read();
        t = IO::read();

        int lca = LCA(x, d);

        int dist = h[x] + h[d] - 2 * h[lca];

        if (dis <= t) x = d;
        else{
            if (h[x] - h[lca] >= t) x = query(x, t);

            else if (h[x] - h[lca] < t) x = query(d, dis - t);
        }

        IO::write(x);
        putchar(' ');       
    }

    return 0;
}