{"problem":{"name":"[北大集训 2021] 经典游戏","description":{"content":"某天，`C` 和 `K` 觉得很无聊，于是决定玩一个经典小游戏： 在一棵有 $n$ 个结点的有根树上，标号为 $i$ 的节点上有 $a_i$ 个棋子。游戏时玩家轮流操作，每次可以将任意一个节点 $u$ 上的一个棋子放置到任意一个点 $v \\in U(u)$上，其中 $U(u)=subtree\\{u\\}\\setminus\\{u\\}$ ，表示 $u$ 的子树内（不包含 $u$ 本身）的点组成的集合。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8994"},"statements":[{"statement_type":"Markdown","content":"某天，`C` 和 `K` 觉得很无聊，于是决定玩一个经典小游戏：\n\n在一棵有 $n$ 个结点的有根树上，标号为 $i$ 的节点上有 $a_i$ 个棋子。游戏时玩家轮流操作，每次可以将任意一个节点 $u$ 上的一个棋子放置到任意一个点 $v \\in U(u)$上，其中 $U(u)=subtree\\{u\\}\\setminus\\{u\\}$ ，表示 $u$ 的子树内（不包含 $u$ 本身）的点组成的集合。不能进行操作者失败。\n\n而 `C` 和 `K` 作为 `P**` 和 `T**` 的在读学生，这种一眼就能找出必胜策略的游戏实在是索然无味，于是两人觉得，每个人给自己一个特殊能力可能会比较有趣：\n\n`C` 在开始游戏之前，**可以选择**将当前树的树根 $R$ 换到与 $R$ 相邻的任意一个点 $R^{\\prime}$ 上。定义两个点相邻当且仅当这两个点有边直接相连。\n\n`K` 在开始游戏之前，**必须选择**树上的一个节点，在上面加上一颗棋子。\n\n`C` 和 `K` 决定玩 $m$ 局游戏。每局游戏的流程如下：\n\n1. 游戏开始前，`C` 和 `K` 会商量好，先在标号为 $x$ 的节点上放上一个棋子，然后将树根设为 $y$。\n2. 之后 `C` 可以选择是否发动特殊能力，`C` 决策完之后 `K` 可以选择是否发动特殊能力。\n3. 特殊能力的决策结束后，会在这棵树上进行一局 `C` 先手、`K` 后手的游戏。游戏完成后会将树上棋子的状态**还原到流程 `1` 结束后的状态**。\n\n`C` 觉得这个游戏可以出成一个简单题，于是他决定考考你：`C` 在每局游戏的第二步的时候，有多少种决策方式使得不管 `K` 如何进行特殊能力的操作，开始游戏时都存在**必胜策略**？两种决策方式不同，**当且仅当**两种决策**更换的树根** $R^{\\prime}$ **不同**，或者**两者中仅有一个没有发动特殊能力**。\n\n## Input\n\n第一行包括一个整数，表示该测试点所在的子任务的分数。你可以使用这个信息判断该测试点满足的特殊性质。特别的，下发样例中此行使用 $0$ 代替。\n\n第二行包含两个用空格隔开的正整数 $n, m$，表示树的节点数目以及游戏的轮数。树上的节点从 $1$ 到 $n$ 编号。\n\n接下来 $n-1$ 行，每行包含两个用空格隔开的正整数 $u_i,v_i$，满足 $1 \\le u_i,v_i \\le n$，表示编号为 $u_i$ 和 $v_i$ 的节点之间有边直接相连。\n\n接下来一行包含 $n$ 个用空格隔开的整数 $a_1,a_2,\\ldots,a_n$，满足 $0 \\leq a_1,a_2,\\ldots,a_n \\leq 10^9$。\n\n接下来 $m$ 行，每行包含两个用空格隔开的正整数 $x, y$ 描述一局游戏，满足 $1 \\le x,y \\le n$。\n\n## Output\n\n你需要输出 $m$ 行，其中第 $i$ 行应当包含一个非负整数 $x$ 表示第 $i$ 局游戏中，`C` 存在多少种使用特殊能力的决策方案，使得 `C` 在这局游戏中存在必胜策略。注意，**不使用特殊能力**也是一种**可能可行**的决策方案。\n\n[samples]\n\n## Background\n\nCTT2021 D4T2\n\n## Note\n\n| 子任务分数 | $1\\le n,m\\le$ | $\\max\\{a_1,a_2,\\dots,a_n\\}\\le$ |              特殊性质              |\n| :--------: | :-----------: | :----------------------------: | :--------------------------------: |\n|    $16$    |      $5$      |              $1$               |                 无                 |\n|    $15$    |     $300$     |              $1$               |                 无                 |\n|    $14$    |    $5000$     |             $10^9$             |                 无                 |\n|    $13$    |   $100000$    |             $10^9$             |        保证给出的树是一条链        |\n|    $12$    |   $100000$    |             $10^9$             | 保证给出的树存在一个点度数为 $n-1$ |\n|    $11$    |   $100000$    |             $10^9$             |   保证 $m$ 次游戏初始给定根一致    |\n|    $10$    |   $500000$    |             $10^9$             |                 无                 |\n|    $9$     |   $1000000$   |             $10^9$             |                 无                 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8994","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"sample_group":[["0\n5 2\n1 2\n1 3\n2 4\n2 5\n1 0 1 0 1\n2 2\n4 4","2\n1\n"],["0\n10 10\n6 3\n7 4\n8 2\n2 1\n9 1\n1 3\n3 4\n4 5\n5 10\n0 0 1 1 1 0 1 1 0 0 \n8 3\n2 3\n7 10\n7 3\n6 7\n8 5\n9 8\n2 10\n5 4\n3 9\n","1\n1\n0\n1\n1\n1\n0\n0\n2\n1\n"]],"created_at":"2026-03-03 11:09:25"}}