题解：P13019 [GESP202506 八级] 树上旅行

流光萤影 · 2025-06-30 21:09:44 · 题解

前言：

本题解使用语言：C++14 O2。

正文：

思路：预处理出从任意一个点向根节点进行第一种移动与向叶子节点进行第二种操作所拼接而成的链。

因为该链即为根节点与从该节点进行第二种移动所能的到达的叶子节点间的路径链，所以可用 mp _ i 记录节点 i 进行第二种移动所能达到的叶子节点的序号，再预处理出根节点到每个叶子节点的路径链。用 Q _ j 表示根节点到叶子节点 j 的路径链，则 Q _ {mp _ i} 表示节点 i 所在的链。

这样一来，我们可通过使用变量 now 记录当前节点在所处链上的位置来映射当前节点的序号（Q _ {mp _ s,now}，其中 s 与当前节点共链）。注意：进行第一种操作后，节点所处链可能改变，需要及时更新。

叶子节点可能很多，多条链可能所含过多的重复点导致 MLE。假设小 A 所在一个叶子节点，该节点的父节点有多个子节点且该节点不是父节点的子节点中序号最小的，那么只要进行一次第一种移动后，小 A 就不可能再回到该叶子节点，所以我们可以通过对此类叶子节点特殊处理从而舍去对根节点到此类叶子节点间的路径链的记录。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int n,q,fa[100005],son[100005],mp[100005],cnt[100005],pos[100005];
vector<int> bridge[100005],Q[100005];
void dfs(int now,int p)
{
    pos[now] = p;
    if(!son[now])
    {
        mp[now] = now;
        return;
    }
    for(int to:bridge[now]) dfs(to,p+1);
    mp[now] = mp[son[now]];
    return;
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> q;
    for(int i(2);i <= n;++i)
    {
        cin >> fa[i];
        if(!son[fa[i]]) son[fa[i]] = i;
        bridge[fa[i]].emplace_back(i);
    }
    dfs(1,0);
    for(int i(1);i <= n;++i) ++cnt[mp[i]];
    for(int i(1);i <= n;++i)
    {
        if(!son[i] && cnt[i] > 1)
        {
            for(int now(i);now;now = fa[now]) Q[i].emplace_back(now);
            reverse(Q[i].begin(),Q[i].end());
        }
    }
    Q[0].emplace_back(1);
    for(int s,k,a,now;q;--q)
    {
        cin >> s >> k;
        bool flag(0);
        if(cnt[mp[s]] == 1)
        {
            flag = 1;
            for(;k;--k)
            {
                cin >> a;
                if(a > 0)
                {
                    s = fa[s];
                    --a;
                    now = pos[s];
                    now += -a;
                    now = min(now,int(Q[mp[s]].size())-1);
                    now = max(now,0);
                    s = Q[mp[s]][now];
                    --k;
                    flag = 0;
                    break;
                }
            }

        }
        else now = pos[s];
        if(flag)
        {
            cout << s << "\n";
            continue;
        }
        for(;k;--k)
        {
            cin >> a;
            now += -a;
            now = min(now,int(Q[mp[s]].size())-1);
            now = max(now,0);
            s = Q[mp[s]][now];
        }
        cout << s << "\n";
    }
}