P10214 [CTS2024] 投票游戏

有 $n$ 个人，由 $1$ 至 $n$ 编号。第 $i (2 \le i \le n)$ 个人有一个讨厌的人 $f_i (1 \leq f_i < i)$，第 $1$ 个人没有讨厌的人。 这一天，$n$ 个人进行了一场关于投票的游戏。一次游戏会进行 $n$ 轮。游戏开始时，所有人都没有被票出。游戏的每一轮中，会进行以下过程： 1. 对于每一个没有被票出的人 $i$，TA 初始有 $a_i$ 票。 2. 随后，对于每一个没有被票出的人 $i$，如果 TA 有讨厌的人且 TA 讨厌的人 $f_i$ 没有被票出，则 TA 会给 $f_i$ 投 $b_i$ 票。 3. 最后，票出当前没有被票出的人的票数最高的，如果有多个票数最高的人，票出其中编号最大的人。 一次游戏的 $n$ 轮之间独立计票。 在游戏开始前，发生了 $q$ 次事件，事件有以下两种： 1. 给定 $p, x, y$，将 $(a_p, b_p)$ 修改为 $(x,y)$； 2. 小明想知道，给定两个人 $c,d$，如果此刻进行一次游戏，两个人中谁先被票出。 作为小明的朋友，你可以帮帮小明吗？

无

无

对于所有测试数据， - $1 \le n, q \le 2 \times 10^5$， - $\forall 2 \le i \le n, 1 \le f_i < i$， - $0 \le a_i, b_i, x, y \le 10^8$， - $1 \le c, d, p \le n$， - $c \ne d$。 | 子任务编号 | 子任务分值 | $n \leq$ | $q \leq$ | 特殊性质 | |-------|-------|-----------------|-----------------|----------------------------| | 1 | 5 | $500$ | $500$ | 无 | | 2 | 10 | $3000$ | $3000$ | 无 | | 3 | 10 | $2 \times 10^5$ | $2 \times 10^5$ | $f_i$ 在 $[1, i - 1]$ 中均匀随机 | | 4 | 15 | $2 \times 10^5$ | $2 \times 10^5$ | $f_i = 1$ | | 5 | 30 | $2 \times 10^5$ | $2 \times 10^5$ | $f_i = i-1$ | | 6 | 30 | $2 \times 10^5$ | $2 \times 10^5$ | 无 |