当前位置: 首页 > news >正文

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;
}

 

http://www.hskmm.com/?act=detail&tid=19212

相关文章:

  • 完整教程:负载均衡式的在线OJ项目编写(二)
  • Java语法基础课程动手动脑及课后实验问题整理文档
  • 安装包制作流程-final
  • 让YOLO飞起来:从CPU到GPU的配置指南
  • 记录这辈子见到的第一道从上到下的树上倍增
  • 06.容器存储 - 教程
  • 1748:约瑟夫问题
  • Ansible + Docker 部署 Apache Nifi 1.28 单用户集群
  • 候机的队伍
  • Keil uVision5 设置 hex 输出路径,不放Objects目录下
  • 垃圾收集器G1ZGC详解
  • 2025海丰杯WP
  • 油猴脚本(tampermonkey)离线安装文件下载,带油猴(tampermonkey)插件清单
  • react useEffect Hook讲解
  • SentinelOne与MITRE ATTCK企业版2025评估的深度解析
  • 详细介绍:Docker的介绍
  • gen-ui-python
  • SPI和普通设计模式区别
  • 2025国内裱纸机厂家最新推荐排行榜:聚焦智能高速与全自动机型,权威精选综合实力 TOP3 厂家
  • 【题解】P13345 [EGOI 2025] IMO
  • 2025电线电缆厂家最新权威推荐榜:聚焦电线电缆实力企业,覆盖多场景需求助力精准选购
  • 9.27课后作业
  • 调度算法,上古三算法
  • 2025 年电脑租赁公司最新推荐排行榜:深度解析 TOP3 优质租电脑公司,助企业个人租赁电脑选择指南
  • 完整教程:✨WPF编程基础【1.2】:XAML中的属性
  • 学位论文中 公式的插入,格式调整、编号以及引用
  • 2025 北京羊蝎子餐厅推荐排行榜:TOP3最新必吃榜单,聚焦朝阳昌平东城等区域,揭秘北京羊蝎子餐厅必吃的门店!
  • 复刻江协激光触发器
  • Eurocrypt 2021 s Accepted Papers
  • Linux云服务器如何手动配置DNS?