题目描述

给定一棵 $n$ 个节点的树。每个节点 $i$ 上可能插着红旗和蓝旗：$a_i=1$ 表示有红旗，$b_i=1$ 表示有蓝旗。一个节点可以同时插两种旗，也可以都不插。

对每一对节点 $x,y$（$1 \le x < y \le n$），记树上 $x$ 到 $y$ 的路径（包含两端）为 $S$。

对于 $S$ 中不是端点的节点 $i$，节点 $i$ 把路径分成两段：$x$ 到 $i$ 之间的部分（含 $x$，不含 $i$）称为 $x$ 侧；$i$ 到 $y$ 之间的部分（不含 $i$，含 $y$）称为 $y$ 侧。

如果其中一侧至少有一个节点插着红旗，并且另一侧至少有一个节点插着蓝旗，就称这条路径关照了节点 $i$。红旗可以在 $x$ 侧，也可以在 $y$ 侧。如果两种方向都满足条件，这条路径对节点 $i$ 仍只计数一次。

注意：节点 $i$ 自己身上的旗子不起作用，路径的端点不会被这条路径关照。

对每个节点 $i$，求有多少条路径关照了它。

输入格式

从文件 hub.in 中读入数据。

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上的一条边。

输出格式

输出到文件 hub.out 中。

输出一行 $n$ 个整数，第 $i$ 个数表示关照节点 $i$ 的路径条数。

样例1输入

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

样例1输出

0 2 4 0 2 0

样例1解释

树的形状是 $1-2-3$，$3$ 再连向 $4$ 和 $5$，$5$ 连向 $6$。红旗在节点 $1,4$，蓝旗在节点 $2,4,6$。

下表列出所有满足条件的“路径与被关照节点”。左右两侧均不包含被关照的节点 $i$。

$i$	$(x,y)$	路径	$x$ 侧	$x$ 侧的旗	$y$ 侧	$y$ 侧的旗
2	$(1,4)$	$1 \to 2 \to 3 \to 4$	$\{1\}$	红	$\{3,4\}$	红、蓝
	$(1,6)$	$1 \to 2 \to 3 \to 5 \to 6$			$\{3,5,6\}$	蓝
3	$(1,4)$	$1 \to 2 \to 3 \to 4$	$\{1,2\}$	红、蓝	$\{4\}$	红、蓝
	$(1,6)$	$1 \to 2 \to 3 \to 5 \to 6$			$\{5,6\}$	蓝
	$(2,4)$	$2 \to 3 \to 4$	$\{2\}$	蓝	$\{4\}$	红、蓝
	$(4,6)$	$4 \to 3 \to 5 \to 6$	$\{4\}$	红、蓝	$\{5,6\}$	蓝
5	$(1,6)$	$1 \to 2 \to 3 \to 5 \to 6$	$\{1,2,3\}$		$\{6\}$
	$(4,6)$	$4 \to 3 \to 5 \to 6$	$\{4,3\}$

节点 $1,4,6$ 都是叶子，只能做路径的端点，所以答案为 $0$。节点 $2,3,5$ 被关照的次数分别为 $2,4,2$，与样例输出一致。

样例2

见选手下发文件夹中的 hub2.in 与 hub2.ans。

样例3

见选手下发文件夹中的 hub3.in 与 hub3.ans。

数据范围

对于所有测试数据，保证 $2 \le n \le 5 \times 10^5$，$a_i,b_i \in \{0,1\}$。

本题共 $24$ 个测试点，采用捆绑测试。只有通过一个子任务内的全部测试点，才能获得该子任务的全部分数；否则该子任务得 $0$ 分。

子任务编号	测试点编号	分值	$n \le$	特殊性质
1	$1 \sim 4$	10	200	无
2	$5 \sim 6$	15	3000
3	$7 \sim 10$		$5 \times 10^5$	A
4	$11 \sim 13$	5		B
5	$14 \sim 16$	20		C
6	$17 \sim 24$	35		无

特殊性质 A：树是一条链，即第 $i$ 条边满足 $u=i,v=i+1$。

特殊性质 B：树是菊花，即每条边都满足 $u=1$。

特殊性质 C：所有 $b_i=1$。