← 返回题目列表

Codeforces · 2006/A

A. 鸢尾花和树上的游戏

中文机器翻译题面 查看原题

Iris 有一个树根在顶点 $$$1$$$。每个顶点的值为 $$$\mathtt 0$$$ 或 $$$\mathtt 1$$$。

让我们考虑树的叶子(顶点 $$$1$$$ 永远不会被视为叶子)并定义其权重。构造一个由从根开始到该叶子结束的路径上的顶点值形成的字符串。那么叶子的权重就是 $$$\mathtt{10}$$$ 和 $$$\mathtt{01}$$$ 子串在其中出现的次数之差。

以下面的树为例。绿色顶点的值为 $$$\mathtt 1$$$,而白色顶点的值为 $$$\mathtt 0$$$。

- 让我们计算叶子$$$5$$$的重量:形成的字符串是$$$\mathtt{10110}$$$。子字符串 $$$\mathtt{10}$$$ 出现的次数是 $$$2$$$,子字符串 $$$\mathtt{01}$$$ 出现的次数是 $$$1$$$,因此差值是 $$$2 - 1 = 1$$$。
- 让我们计算叶子$$$6$$$的重量:形成的字符串是$$$\mathtt{101}$$$。子字符串 $$$\mathtt{10}$$$ 出现的次数是 $$$1$$$,子字符串 $$$\mathtt{01}$$$ 出现的次数是 $$$1$$$,因此差值是 $$$1 - 1 = 0$$$。

树的得分定义为树中权重非零的叶子的数量。

但有些顶点的值尚未确定,将以 $$$\texttt{?}$$$ 的形式提供给您。填空太无聊了,所以艾丽丝打算邀请朵拉玩一个游戏。在每一回合中,其中一个女孩选择任何剩余的值为 $$$\texttt{?}$$$ 的顶点,并将其值更改为 $$$\mathtt{0}$$$ 或 $$$\mathtt{1}$$$,其中 Iris 先行。游戏继续进行,直到树中不再有值为 $$$\mathtt{?}$$$ 的顶点。艾里斯的目标是最大化树的分数,而朵拉的目标是最小化它。

假设两个女孩都发挥最佳,请确定树的最终得分。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5\cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — 树中的顶点数。

以下 $$$n - 1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$) - 表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。

保证给定的边形成一棵树。

最后一行包含长度为 $$$n$$$ 的字符串 $$$s$$$。 $$$s$$$ 的第 $$$i$$$ 个字符表示顶点 $$$i$$$ 的值。保证 $$$s$$$ 仅包含字符 $$$\mathtt{0}$$$、$$$\mathtt{1}$$$ 和 $$$\mathtt{?}$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 树的最终分数。

示例

输入 #1

6
4
1 2
1 3
4 1
0101
4
1 2
3 2
2 4
???0
5
1 2
1 3
2 4
2 5
?1?01
6
1 2
2 3
3 4
5 3
3 6
?0????
5
1 2
1 3
1 4
1 5
11?1?
2
2 1
??

输出 #1

2
1
1
2
1
0

注意

在第一个测试用例中,所有顶点的值都已确定。从根到叶共有三种不同的路径:

- 从顶点 $$$1$$$ 到顶点 $$$2$$$。路径形成的字符串为$$$\mathtt{01}$$$,因此叶子的权重为$$$0-1=-1$$$。
- 从顶点 $$$1$$$ 到顶点 $$$3$$$。路径形成的字符串为$$$\mathtt{00}$$$,因此叶子的权重为$$$0-0=0$$$。
- 从顶点 $$$1$$$ 到顶点 $$$4$$$。路径形成的字符串为$$$\mathtt{01}$$$,因此叶子的权重为$$$0-1=-1$$$。

因此,有两个权重非零的叶子,因此树的得分为$$$2$$$。

在第二个测试用例中,两个玩家的最佳选择序列之一可以是:

- Iris 选择将顶点 $$$3$$$ 的值更改为 $$$\mathtt 1$$$。
- Dora 选择将顶点 $$$1$$$ 的值更改为 $$$\mathtt 0$$$。
- Iris 选择将顶点 $$$2$$$ 的值更改为 $$$\mathtt 0$$$。

最终的树如下:

唯一权重非零的叶子是$$$3$$$,因此树的得分是$$$1$$$。请注意,这可能不是 Iris 和 Dora 的唯一最佳选择序列。