UOJ Logo Universal Online Judge

UOJ

#719. 【北大集训2021】经典游戏

附件下载 统计

某天,CK 觉得很无聊,于是决定玩一个经典小游戏:

在一棵有 $n$ 个结点的有根树上,标号为 $i$ 的节点上有 $a_i$ 个棋子。游戏时玩家轮流操作,每次可以将任意一个节点 $u$ 上的一个棋子放置到任意一个点 $v \in U(u)$上,其中 $U(u)=subtree\{u\}\setminus\{u\}$ ,表示 $u$ 的子树内(不包含 $x$ 本身)的点组成的集合。不能进行操作者失败。

CK 作为 P**T** 的在读学生,这种一眼就能找出必胜策略的游戏实在是索然无味,于是两人觉得,每个人给自己一个特殊能力可能会比较有趣:

C 在开始游戏之前,可以选择将当前树的树根 $R$ 换到与 $R$ 相邻的任意一个点 $R^{\prime}$ 上。定义两个点相邻当且仅当这两个点有边直接相连。

K 在开始游戏之前,必须选择树上的一个节点,在上面加上一颗棋子。

CK 决定玩 $m$ 局游戏。每局游戏的流程如下:

  1. 游戏开始前,CK 会商量好,先在标号为 $x$ 的节点上放上一个棋子,然后将树根设为 $y$。
  2. 之后 C 可以选择是否发动特殊能力,C 决策完之后 K 可以选择是否发动特殊能力。
  3. 特殊能力的决策结束后,会在这棵树上进行一局 C 先手、K 后手的游戏。游戏完成后会将树上棋子的状态还原到流程 1 结束后的状态

C 觉得这个游戏可以出成一个简单题,于是他决定考考你:C 在每局游戏的第二步的时候,有多少种决策方式使得不管 K 如何进行特殊能力的操作,开始游戏时都存在必胜策略?两种决策方式不同,当且仅当两种决策更换的树根 $R^{\prime}$ 不同,或者两者中仅有一个没有发动特殊能力

输入格式

从标准输入读入数据。

第一行包括一个整数,表示该测试点所在的子任务的分数。你可以使用这个信息判断该测试点满足的特殊性质。特别的,下发样例中此行使用 $0$ 代替。

第二行包含两个用空格隔开的正整数 $n, m$,表示树的节点数目以及游戏的轮数。树上的节点从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行,每行包含两个用空格隔开的正整数 $u_i,v_i$,表示编号为 $u_i$ 和 $v_i$ 的节点之间有边直接相连。

接下来一行包含 $n$ 个用空格隔开的整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行,每行包含两个用空格隔开的正整数 $x, y$ 描述一局游戏。

输出格式

输出到标准输出。

你需要输出 $m$ 行,其中第 $i$ 行应当包含一个非负整数 $x$ 表示第 $i$ 局游戏中,C 存在多少种使用特殊能力的决策方案,使得 C 在这局游戏中存在必胜策略。注意,不使用特殊能力也是一种可能可行的决策方案。

样例

input

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

output

2
1

explanation

第一局游戏中,C 存在两种胜利的方式:不使用特殊能力,或者将根节点换到一号点上。

第二局游戏中,C 只有一种胜利的方式:将根节点换到二号点上。

样例二、三、四

见附件下载。

数据范围与提示

子任务分数 $1 \le n,m \le$ $\max\{a_1,a_2,\ldots,a_n\}\le$ 特殊性质
$16$ $5$ $1$
$15$ $300$
$14$ $5000$ $10^9$
$13$ $100000$ 保证给出的树是一条链
$12$ 保证给出的树存在一个点度数为 $n-1$
$11$ 保证 $m$ 次游戏初始给定根一致
$10$ $500000$
$9$ $1000000$

对于所有数据,保证 $1\leq n,m\leq 1000000, 0 \leq a_1,a_2,\ldots,a_n \leq 10^9, 1 \le u_i,v_i \le n, 1 \le x,y \le n$。

hack

hack 数据的第一行必须是 $9$。

时间限制:$~~4s~~\texttt{8s}$

空间限制:$\texttt{512MB}$