P13019 [GESP202506 八级] 树上旅行

解题思路

这个问题需要在有根树上模拟移动操作，但直接模拟会超时（因为移动次数可能很大）。核心思想是使用二进制提升（Binary Lifting）技术来优化移动过程。

关键观察：

1. 向上移动（移动到父节点）：可以使用倍增表 f[i][j] 表示从节点 i 向上移动 2^j 步到达的节点

2. 向下移动（移动到最小子节点）：可以使用倍增表 d[i][j] 表示从节点 i 向下移动 2^j 步（每次都走最小子节点）到达的节点

算法步骤：

1. 预处理：构建两个倍增表

   • f[i][j]：向上移动的倍增表

   • d[i][j]：向下移动的倍增表

2. 查询处理：对于每个移动序列，使用倍增表快速计算最终位置

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int N = 2e5 + 10, inf = 0x3f3f3f3f;
int n, q;
vector<int> g[N];  // 存储每个节点的子节点
int fa[N], son[N]; // 父节点和子节点信息
int f[N][25];      // 向上移动的倍增表：f[i][j] 表示从i向上移动2^j步到达的节点
int dep[N], d[N][25]; // d[i][j] 表示从i向下移动2^j步（走最小子节点）到达的节点// DFS预处理倍增表
void dfs(int x, int fat)
{// 初始化向上移动的倍增表f[x][0] = fat;for(int i = 1; i <= 20; i++){int y = f[x][i - 1];f[x][i] = f[y][i - 1];  // 倍增：2^i = 2^(i-1) + 2^(i-1)
    }// 递归处理子节点for(int i = 0; i < g[x].size(); i++){int y = g[x][i];dfs(y, x);}// 初始化向下移动的倍增表if(g[x].size() >= 1) d[x][0] = g[x][0];  // 第一步向下移动到最小子节点else d[x][0] = x;        // 叶子节点无法向下移动// 构建向下移动的倍增表for(int i = 1; i <= 20; i++){int y = d[x][i - 1];d[x][i] = d[y][i - 1];  // 倍增原理
    }
}// 向上移动op步
int up(int s, int op)
{// 使用二进制分解快速计算for(int i = 20; i >= 0; i--){if(op >= (1 << i)){  // 如果剩余步数 >= 2^iop -= (1 << i);s = f[s][i];     // 一次性移动2^i步
        }}return max(s, 1);  // 保证不会移动到根节点之上
}// 向下移动op步（沿着最小子节点路径）
int down(int s, int op)
{// 如果是叶子节点，无法向下移动if(d[s][0] == s) return s;// 使用二进制分解快速计算for(int i = 20; i >= 0; i--){if(op >= (1 << i)){  // 如果剩余步数 >= 2^iop -= (1 << i);s = d[s][i];     // 一次性向下移动2^i步
        }}return s;
}int main()
{cin >> n >> q;// 读入树结构for(int i = 2; i <= n; i++){int x; cin >> x;g[x].push_back(i);  // 添加子节点fa[i] = x;          // 记录父节点
    }// 对每个节点的子节点排序，确保第一个是最小编号的子节点for(int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());fa[1] = 1;  // 根节点的父节点设为自身dfs(1, 0);  // 从根节点开始DFS预处理// 处理每个查询while(q--){int s, k; cin >> s >> k;  // 起点和移动序列长度for(int i = 1; i <= k; i++){int op; cin >> op;  // 移动操作if(op > 0) s = up(s, op);    // 向上移动else s = down(s, -op); // 向下移动（取绝对值）
        }cout << s << endl;  // 输出终点
    }return 0;
}