[R76F]信号分区 - 代码源竞赛平台

时空限制

1S/512M

题目描述

林区内的 $n$ 座信号站通过双向线路连成一棵树，信号站编号为 $1$ 到 $n$。每座信号站采用 $0$ 或 $1$ 两种模式之一。

工作人员至多进行一次调整：选择两座信号站 $u,v$，将它们之间简单路径上的所有信号站同时切换模式，即 $0$ 变为 $1$，$1$ 变为 $0$。允许 $u=v$，此时只调整这一座信号站；也可以不进行调整。

随后，断开所有连接不同模式信号站的线路。剩余线路连接在一起的信号站组成一个独立分区，单独一座信号站也算一个分区。

请计算最终最多能够得到多少个独立分区。

格式

输入格式

第一行包含一个整数 $n$。

第二行包含一个长度为 $n$ 的字符串 $c$，第 $i$ 个字符表示信号站 $i$ 的模式。

接下来 $n-1$ 行，每行包含两个整数 $u,v$，表示信号站 $u$ 与 $v$ 之间有一条双向线路。

输出格式

输出一个整数，表示能够得到的最大分区数量。

样例

样例输入 #1

5
00000
1 2
1 3
1 4
1 5

样例输出 #1

5

样例解释 #1

只切换信号站 $1$ 的模式，所有线路的两端模式都不同，断开后得到 $5$ 个单站分区。

样例输入 #2

4
0101
1 2
2 3
3 4

样例输出 #2

4

样例解释 #2

不进行调整即可得到 $4$ 个分区。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$20$	$300$	无
$2$	$30$	$2 \times 10^5$	特殊性质 A
$3$	$50$		无

特殊性质 A：原树是一条链，即每个顶点的度数不超过 $2$。

对于 $100\%$ 的数据，满足 $1 \le n \le 2 \times 10^5$，字符串 $c$ 长度为 $n$ 且只含 0 和 1，每条边的端点满足 $1 \le u,v \le n$，输入的 $n-1$ 条边构成一棵无向树。