#2241. 网格

    ID: 2241 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>TEAM赛事:contest3163来源:qoj.ac数据:公开样例树上算法倍增

网格

网格

题目描述

给定一个 层的三角形网格,第 ( )层的点分别编号为 。 对于除了最后一层以外的每个点 ,有两条到达下一层的边,左侧的边为 ,右侧 的边为 。 在 处有一个球,将选择 条不同的路径到达最后一层。初始时选择的路径为全部向右侧到达 下一层,即 。对于 ,第 条路径与第 条路径仅有到 达 层时选择的方向不同。例如,若 ,则第 条路径为 。 给定一个 的排列 ,可以发现,所有的 条路径恰好到达第 层的所有结点, 且网格中的所有点构成一棵有根树的结构。有 次询问,每次询问给定两个网格中的点 与 ,求这两个点在有根树上的最近公共祖先。 输入格式 输出格式 样例输入 3 2 3 1 5 3 3 3 0 2 2 2 1 1 0 3 1 3 1 3 2 2 2 2 2 样例输出 0 0 1 1 0 0 2 1 2 2 样例解释 子任务 子任务 分 特殊性质 编号 值 无 无 存在 ,使得 无 无 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2 3 1
5
3 3 3 0
2 2 2 1
1 0 3 1
3 1 3 2
2 2 2 2
0 0
1 1
0 0
2 1
2 2