#5767. 「CEOI2026」观鸟者

标签: 传统 | 时间限制: 10000 ms | 内存限制: 512 MiB |

题目描述

题目译自 CEOI 2026 Day1 T1「Birdwatchers」

San Serriffe 的观鸟者协会拥有一个奇特、臃肿且不断变动的内部组织结构。协会由 $n$ 个分会组成，每位协会成员都恰好属于一个分会。分会按 $1$ 到 $n$ 进行编号，第 $i$ 个分会有 $m_i$ 名成员。因此，协会共有 $M = m_1 + m_2 + \dots + m_n$ 名成员。

每个分会由其一名成员领导，在此角色中被称为该分会的干事。干事的编号与分会相同，因此对于每个 $i = 1, \dots, n$，干事 $i$ 是负责第 $i$ 个分会的人。

此外，干事之间通过导师系统建立起层级结构：除一人外，每个干事都有一个导师，该导师是另一个分会的干事。唯一没有导师的干事是协会会长。若干事 $a$ 是干事 $b$ 的导师，我们也可以说干事 $b$ 是干事 $a$ 的门徒。没有任何干事会直接或间接成为自己的导师；因此，通过追溯从某个干事到其导师、导师的导师等序列，最终总是会到达会长。

我们定义一名干事的影响力为其所属分会的成员数量与其所有门徒（如果有的话）的影响力之和。显而易见，影响力最大的干事是会长，其影响力始终等于 $M$。若一名干事的影响力满足 $\geq M / 2$，则称其为资深干事。

协会章程规定，在所有资深干事中，影响力最小的那一位将担任协会的财务主管。

干事（会长除外）有时可能会改变其归属，从而成为与之前不同的另一位导师的门徒（前提是其新导师不是其门徒或门徒的门徒等）。因此，某些干事的影响力可能会发生变化，财务主管的职责也可能落到与之前不同的干事身上。

编写一个程序，读取协会的初始状态及一系列归属变更。你的程序必须输出初始状态下以及每次归属变更后的财务主管编号。

输入格式

第一行包含两个整数 $n$ 和 $q$，用空格分隔，分别表示分会的数量和归属变更的次数。

接下来 $n$ 行描述协会的初始状态。其中第 $i$ 行包含两个整数 $s_i$ 和 $m_i$，用空格分隔；$s_i$ 是干事 $i$（即负责第 $i$ 个分会的干事）的导师，而 $m_i$ 是第 $i$ 个分会的成员数量。若 $s_i = 0$，则表示干事 $i$ 是协会会长，因而没有导师。

其余 $q$ 行描述归属的变更。其中第 $j$ 行包含两个整数 $\hat{x}_j$ 和 $\hat{z}_j$，用空格分隔。这两个整数的含义如下：设 $t_j$（对于 $j = 0, \dots, q$）表示前 $j$ 次归属变更后的财务主管（因此 $t_0$ 为第一次归属变更之前的初始财务主管）。则第 $j$ 次归属变更代表干事 $z_j$ 成为干事 $x_j$ 的新导师，其中 $x_j = 1 + ((t_{j-1} + \hat{x}_j) \bmod n)$ 且 $z_j = 1 + ((t_{j-1} + \hat{z}_j) \bmod n)$。这种对 $x_j$ 和 $z_j$ 值的表达方式旨在强制你的程序按照变更出现的顺序依次处理它们。

输入数据中的归属变更总是有效的，即 $z_j$ 不会等于 $x_j$，且 $z_j$ 也不会是 $x_j$ 的门徒、门徒的门徒等。但是，在第 $j$ 次变更之前 $z_j$ 可能已经是 $x_j$ 的导师（在这种情况下，实际上没有任何变化）。

请注意，若你的程序在某个时刻计算出了错误的答案 $t_j$，则后续的输入 $\hat{x}_{j+1}, \hat{z}_{j+1}$ 等也将被错误地解码，并且可能因为解码后的输入无效（例如错误地得到了一个属于 $x_{j+1}$ 门徒的 $z_{j+1}$）而导致程序以 RTE（运行错误）而非 WA（答案错误）判定终止。

输出格式

输出 $t_0, t_1, \dots, t_q$，每行包含一个整数，其中 $t_j$ 表示前 $j$ 次归属变更后的财务主管编号。显然，每个 $t_j$ 必须是范围 $1 \leq t_j \leq n$ 内的整数。

样例

输入

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

输出

2
2
3

起初，干事 $2$ 是财务主管（因此 $t_0 = 2$）。在第一次归属变更中，我们读取 $\hat{x}_1 = 3$ 和 $\hat{z}_1 = 7$，并计算出 $x_1 = 1 + ((2 + 3) \bmod 7) = 6$ 且 $z_1 = 1 + ((2 + 7) \bmod 7) = 3$；因此，干事 $3$ 成为干事 $6$ 的新导师；干事 $2$ 仍为财务主管（因此 $t_1 = 2$）。在第二次归属变更中，我们读取 $\hat{x}_2 = 2$ 和 $\hat{z}_2 = 7$，并计算出 $x_2 = 1 + ((2 + 2) \bmod 7) = 5$ 且 $z_2 = 1 + ((2 + 7) \bmod 7) = 3$；因此，干事 $3$ 成为干事 $5$ 的新导师，并同时也成为了新的财务主管（因此 $t_2 = 3$）。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq n \leq 1000000$
• $1 \leq q \leq 30000$
• 对于每个 $i = 1, \dots, n$，满足 $1 \leq m_i$
• $m_1 + m_2 + \dots + m_n \leq 10^9$
• 对于每个 $j = 1, \dots, q$，满足 $1 \leq \hat{x}_j \leq n$ 且 $1 \leq \hat{z}_j \leq n$

详细子任务附加限制及分值如下表所示。