P13019 - 树上旅行 题解
序言
萌新第一篇题解，将分享一种与全部已有题解不同的方案（类似链式拆分，考场做法）。
题意简述
给定一颗有根树，树上执行允许执行多次旅行，每次旅行有一个两种操作组成的序列：
- 重复多次移动到父节点（在根节点时位置不变）；
- 重复多次移动到编号最小子节点（在叶子节点时位置不变）。
求旅行结束后的位置。
部分分一
考虑暴力做法，预存每一个节点的父节点和最靠左字节点，递归
int up(int s,int c){
if(c==0||s==1)return s;
return up(parent[s],c-1);
}
int down(int s,int c){
if(c==0||son[s]==INT_MAX)return s;
return down(son[s],c-1);
}for(int i=2;i<=n;i++){
cin>>parent[i];
if(i<son[parent[i]])son[parent[i]]=i;
}部分分二
尝试把树拆分为一条条链：维护一个 map 作为节点到链的映射，遍历每一个节点，检查当前节点是否在链上，如果在链上则跳过，否则依次查找它的首个子节点，将子节点加入到链中，直到叶子节点。
因为每一次创建都会一次性找到叶子节点，而且不能从已经位于链上的节点创建链，所以每个节点都一定对应且只对应一条链，如此存储合适。 如图，考虑题目样例二
- 从
1 开始构建-
1$ 的唯一子节点是 $5$ ,添加 $5 -
5$ 的唯一子节点是 $2$ ,添加 $2 - 以此类推，分别加入
4,3,6 -
-
- 构建出第一条链（同时标记了这些节点的对应第一条链）：
1\rightarrow5\rightarrow2\rightarrow4\rightarrow3\rightarrow6\rightarrow7
-
-
- 从
8 开始构建-
- 构建出第二条链（并标记
8 在第二条链上）：8
-
核心代码：
for(int i=1;i<=n;i++){
if(!down_mp.count(i)){
vector<int>c_chain;
int s=down_chains.size();
int idx=0;
for(int node=i;node!=INT_MAX;node=son[node]){
c_chain.push_back(node);
down_mp[node]={s,idx++};//idx:保存在链上的编号，便于查询
}
down_chains.push_back(c_chain);
}
}对于查询处理：
- 对于向下的查询，直接从表中找出对应的链和链上位置，加上移动量并移动（如果超过链长度说明在叶子节点，就移动至链尾）；
- 对于向上的查询，从表中找出对应的链和位置，减去移动量后，如果是有效索引就直接移动，如果超出链范围则暴力查找（后文考虑跳链）
核心代码：
if(op>0){
auto c_chain=down_chains[down_mp[s].first];
int idx=down_mp[s].second-op;
if(idx<0){
s=up(c_chain[0],-idx);//暴力处理剩余部分
}else{
s=c_chain[idx];
}
}else if(op<0){
op=-op;
auto c_chain=down_chains[down_mp[s].first];
int pos=down_mp[s].second+op;
if(pos>=c_chain.size()){
s=c_chain.back();
}else{
s=c_chain[pos];
}
}可得部分分
正解
在上一部分的做法中，对于无法在一条链中处理完的移动，会"回退"到暴力查找，进而超时。
因为链首节点（根除外）不是最小子节点，所以预处理时会把它另外分一条链。
由此，我们可以尝试在每一条链中尽可能多的向上查找如果仍有剩余步数停在链头，就从链头节点的父节点所在链继续查找，直到用完步数或到达根。
核心代码：
if(op > 0) {
while(op > 0 && s != 1) {
auto& c_chain = down_chains[down_mp[s].first];
int steps = min(op, down_mp[s].second);
if(steps > 0) {
s = c_chain[down_mp[s].second - steps];
op -= steps;
} else {
op--;
s = parent[c_chain[0]];
}
}
}可得满分
常数优化
因为每一个节点都一定属于唯一的一条链，所以可以把链对应表 down_mp 外层改为静态数组而非 map，down_chains 同理。
AC记录及完整代码附上：
#include<bits/stdc++.h>
using namespace std;
int parent[100005];
int son[100005];
pair<int,int> down_mp[100005];
int n,q;
vector<int> down_chains[100005];
int chain_count = 0;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
parent[1] = 0;
for(int i = 0; i <= n+1; i++) son[i] = INT_MAX;
for(int i = 2; i <= n; i++) {
cin >> parent[i];
if(i < son[parent[i]]) son[parent[i]] = i;
}
for(int i = 1; i <= n; i++) {
if(down_mp[i].first == 0 && down_mp[i].second == 0) {
int s = chain_count++;
int idx = 0;
for(int node = i; node != INT_MAX; node = son[node]) {
down_chains[s].push_back(node);
down_mp[node] = {s, idx++};
}
}
}
while(q--) {
int s, k, op;
cin >> s >> k;
while(k--) {
cin >> op;
if(op > 0) {
while(op > 0 && s != 1) {
auto& c_chain = down_chains[down_mp[s].first];
int steps = min(op, down_mp[s].second);
if(steps > 0) {
s = c_chain[down_mp[s].second - steps];
op -= steps;
} else {
op--;
s = parent[c_chain[0]];
}
}
} else if(op < 0) {
op = -op;
auto& chain_info = down_mp[s];
auto& c_chain = down_chains[chain_info.first];
int pos = chain_info.second + op;
if(pos >= c_chain.size()) {
s = c_chain.back();
} else {
s = c_chain[pos];
}
}
}
cout << s << endl;
}
return 0;
}