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

· · 题解

听说 NOIP 考前写题解有助于 rp++。（划掉 (/▽＼)）

前置知识：树链剖分（重链剖分）、树剖求 LCA、树剖求 K 级祖先。

不会也没关系哦，可以看看窝的博客啊（无耻地贴上链接）：树链剖分以及求 LCA、树上 K 级祖先。可以帮忙点个赞赞吗 (/▽＼)。

会用到的记号：

题意简述

有一棵无根树，我们需要动态地维护一枚棋子在树上跳动的过程。单次跳动操作会给定目标节点 d 与最大步数 t，如果能在步数 t 以内走到 d，那么棋子就跳到 d，否则棋子能跳多少是多少。

思路分析

既然这题是无根树，那我们首先随意钦定一个节点为根节点（比如我们这里就选择 1 号节点啦）。然后树剖一下，我们就能方便地求出 LCA 等信息了。

我们先分析分析题目，看看我们需要实现什么操作。

首先比较容易的是当点 m 与 d 之间的距离小于等于 t 时，我们直接可以跳到 d。

嗯嗯，那如果跳不到呢？我们肯定还是要在 m 到 d 的路径上跳的。这个时候我们就需要根据位置来分类讨论一下。

因为蒟蒻比较笨，这里分讨的稍微细了一点（有好好配图讲解哦）。

第一种情况，\text{LCA}(d,m)=d。这时候我们跳 t 步即停止：

第二种情况，\text{LCA}(d,m)=m。这时候是恰好与第一种情况反过来的：

第三种情况，那么就是正常的 LCA 情况。我们将这个路径视为两段 m\to \text{LCA}(d,m)、\text{LCA}(d,m)\to d。根据分讨 t 与 \text{Dist}(m,\text{LCA}(d,m)) 的大小关系，有：

综上所述，我们只用实现求 LCA、距离、K 级祖先啦 (●'◡'●)！

代码实现

鹅……这里蒟蒻在实现的时候实际上是把一开始 \text{Dist}(d,m)\le t 的情况放在了三种情况里面了。单独拎出来也是可以的。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, m, k;
vector<int> e[N];
int dep[N], fa[N], siz[N], hs[N];
int top[N], id[N], ID[N], cnt;
void dfs1(int u, int father)//树剖 
{
    dep[u] = dep[father] + 1, fa[u] = father, siz[u] = 1;
    int maxson = -1;
    for(auto i : e[u])
    {
        if(i == father) continue;
        dfs1(i, u);
        siz[u] += siz[i];
        if(maxson < siz[i]) maxson = siz[i], hs[u] = i;
    }
}
void dfs2(int u, int topf)
{
    top[u] = topf, id[u] = ++ cnt, ID[cnt] = u;
    if(hs[u] == 0) return;
    dfs2(hs[u], topf);
    for(auto i : e[u])
    {
        if(i == fa[u] || i == hs[u]) continue;
        dfs2(i, i);
    }
}
int LCA(int x, int y)//树剖求 LCA 
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    if(dep[x] < dep[y]) return x;
    else return y;
}
int Dist(int x, int y, int lca)//求 Dist(x,y) 
{
    return dep[x] + dep[y] - 2 * dep[lca];
}
int faK(int x, int K)//求 fa(x,K) 
{
    while(id[x] - id[top[x]] + 1 <= K && x != 1)
    {
        K -= (id[x] - id[top[x]] + 1);
        x = fa[top[x]];
    }
    return ID[id[x] - K];
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i < n; i ++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    while(k --)
    {
        int d, t;
        scanf("%d%d", &d, &t);
        int lca = LCA(d, m);
        int dist = Dist(d, m, lca);
        if(lca == d)//情况一 
        {
            if(dist <= t) m = d;
            else m = faK(m, t);
        }
        else if(lca == m)//情况二 
        {
            if(dist <= t) m = d;
            else m = faK(d, dist - t);
        }
        else//情况三 
        {
            if(dist <= t) m = d;
            else
            {
                int D1 = dep[m] - dep[lca];
                int D2 = dep[d] - dep[lca];
                if(D1 <= t)
                {
                    m = lca, t -= D1;
                    m = faK(d, D2 - t);
                }
                else m = faK(m, t);
            }
        }
        printf("%d ", m);
    }
    return 0;
}