[R62E]树 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一棵包含 $n$ 个结点的树，结点的编号为 $1$ 到 $n$。树上的每个结点都被染成了红色或白色。

我们称一条简单路径是“好路径”，当且仅当该路径上（包含两端点）的红色结点数量为偶数，且至少包含 $2$ 个红色结点。

这里一条简单路径由一对无序结点对 $\{u, v\}$（满足 $u \neq v$）唯一确定。请你求出整棵树中满足条件的“好路径”数量。

格式

输入格式

第一行包含一个正整数 $n$，表示树的结点数。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$。其中 $c_i$ 表示第 $i$ 个结点的颜色：若 $c_i = 1$ 则表示结点 $i$ 为红色；若 $c_i = 0$ 则表示结点 $i$ 为白色。

接下来 $n-1$ 行，每行包含两个正整数 $u$ 和 $v$，表示树上结点 $u$ 和 $v$ 之间存在一条边。

输出格式

输出一行一个整数，表示满足条件的“好路径”数量。

样例

样例输入 #1

4
0 0 1 1
1 2
2 3
3 4

样例输出 #1

3

数据规模

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

子任务编号	分数	$n\le$
$1$	$40$	$2000$
$2$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$c_i \in \{0, 1\}$，保证输入给出一个树。