当前没有测试数据。

Ex - 球的收集者

得分：625分

问题描述

给定一个具有 $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$），都要拿起放在那里的一个球。找到拿起的球上被写下的不同整数的最大数量。

约束

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

输入

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

$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