{"problem":{"name":"[CTS2024] 投票游戏","description":{"content":"有 $n$ 个人，由 $1$ 至 $n$ 编号。第 $i (2 \\le i \\le n)$ 个人有一个讨厌的人 $f_i (1 \\leq f_i < i)$，第 $1$ 个人没有讨厌的人。 这一天，$n$ 个人进行了一场关于投票的游戏。一次游戏会进行 $n$ 轮。游戏开始时，所有人都没有被票出。游戏的每一轮中，会进行以下过程： 1. 对于每一个没有被票出的人 $i$，TA 初始有 $a_i$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10214"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 个人，由 $1$ 至 $n$ 编号。第 $i (2 \\le i \\le n)$ 个人有一个讨厌的人 $f_i (1 \\leq f_i < i)$，第 $1$ 个人没有讨厌的人。\n\n这一天，$n$ 个人进行了一场关于投票的游戏。一次游戏会进行 $n$ 轮。游戏开始时，所有人都没有被票出。游戏的每一轮中，会进行以下过程：\n\n1. 对于每一个没有被票出的人 $i$，TA 初始有 $a_i$ 票。\n2. 随后，对于每一个没有被票出的人 $i$，如果 TA 有讨厌的人且 TA 讨厌的人 $f_i$ 没有被票出，则 TA 会给 $f_i$ 投 $b_i$ 票。\n3. 最后，票出当前没有被票出的人的票数最高的，如果有多个票数最高的人，票出其中编号最大的人。\n\n一次游戏的 $n$ 轮之间独立计票。\n\n在游戏开始前，发生了 $q$ 次事件，事件有以下两种：\n\n1. 给定 $p, x, y$，将 $(a_p, b_p)$ 修改为 $(x,y)$；\n2. 小明想知道，给定两个人 $c,d$，如果此刻进行一次游戏，两个人中谁先被票出。\n\n作为小明的朋友，你可以帮帮小明吗？\n\n## Input\n\n从标准输入读入数据。\n\n第一行两个正整数 $n, q$，表示人数与发生的事件数。\n\n第二行 $(n-1)$ 个整数 $f_2, f_3, \\cdots, f_n$。\n\n第三行 $n$ 个整数 $a_1, a_2, \\cdots, a_n$。\n\n第四行 $n$ 个整数 $b_1, b_2, \\cdots, b_n$。\n\n接下来 $q$ 行，每行三个或四个整数描述一个事件。第一个正整数 $op$ 表示发生事件的类型。\n\n- 若 $op=1$，则接下来三个整数 $p, x, y$，表示将 $(a_p, b_p)$ 修改为 $(x, y)$。\n- 若 $op=2$，则接下来两个正整数 $c, d$，你需要判断如果此时进行了一次游戏，$c$ 和 $d$ 谁先被票出。\n\n## Output\n\n输出到标准输出。\n\n对于每个 $op=2$ 的事件输出一行一个 `01` 字符，若 $c$ 先被票出输出 `0`，否则输出 `1`。\n\n[samples]\n\n## Note\n\n对于所有测试数据，\n\n- $1 \\le n, q \\le 2 \\times 10^5$，\n- $\\forall 2 \\le i \\le n, 1 \\le f_i < i$，\n- $0 \\le a_i, b_i, x, y \\le 10^8$，\n- $1 \\le c, d, p \\le n$，\n- $c \\ne d$。\n\n| 子任务编号 | 子任务分值 | $n \\leq$        | $q \\leq$        | 特殊性质                       |\n|-------|-------|-----------------|-----------------|----------------------------|\n| 1     | 5     | $500$           | $500$           | 无                          |\n| 2     | 10    | $3000$          | $3000$          | 无                          |\n| 3     | 10    | $2 \\times 10^5$ | $2 \\times 10^5$ | $f_i$ 在 $[1, i - 1]$ 中均匀随机 |\n| 4     | 15    | $2 \\times 10^5$ | $2 \\times 10^5$ | $f_i = 1$                  |\n| 5     | 30    | $2 \\times 10^5$ | $2 \\times 10^5$ | $f_i = i-1$                |\n| 6     | 30    | $2 \\times 10^5$ | $2 \\times 10^5$ | 无                          |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10214","tags":["2024","CTSC/CTS"],"sample_group":[["5 8\n1 2 3 2\n1 3 2 1 0\n0 4 1 0 0\n2 1 3\n1 1 0 3\n2 2 5\n1 1 2 2\n2 4 3\n2 5 4\n2 5 1\n2 2 1\n","0\n0\n1\n1\n1\n1\n"]],"created_at":"2026-03-03 11:09:25"}}