收集球

题目描述

我们有一棵 $N$ 个顶点的树。第 $i$ 条边 $(1 \le i \le N-1)$ 是连接顶点 $U_i$ 和 $V_i$ 的无向边。顶点 $i$ $(1 \le i \le N)$ 上放着一个写有 $A_i$ 的球和一个写有 $B_i$ 的球。

对于每个 $v = 2,3,\dots,N$，回答下面的问题。（每个查询相互独立。）

考虑从顶点 $1$ 沿最短路径走到顶点 $v$。每经过一个顶点（包括顶点 $1$ 和 $v$），你都要拿起放在那里的一只球。求拿起的球上写着的不同整数的最大个数。

输入格式

输入按以下格式从标准输入给出：

$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_N$ $B_N$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{N-1}$ $V_{N-1}$

输出格式

用空格分隔，在一行中输出 $v=2,3,\dots,N$ 的答案。

样例

4
1 2
2 3
3 1
1 2
1 2
2 3
3 4

2 3 3

例如，当 $v=4$ 时，你会经过顶点 $1,2,3,4$。通过选择写有 $A_1,B_2,B_3,B_4$（即 $1,3,1,2$）的球，球上不同整数的个数为 $3$，这是最大值。

10
2 5
2 2
8 8
4 3
6 10
8 1
9 10
1 7
9 3
5 10
9 3
1 9
3 6
4 1
3 8
10 9
5 4
7 2
9 7

4 3 2 3 4 3 4 2 3

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i,B_i \le N$
• 给定的图是一棵树。
• 输入中的所有值均为整数。