AT_codequeen2023_final_c Path Intersection

给你一棵有 $N$ 个顶点的树，每个顶点编号为 $1, 2, \ldots, N$，以及两个顶点编号 $S, T$。对于 $i = 1, 2, \ldots, N-1$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 对于树中每一个顶点 $j$，请你回答如下问题： - 从顶点 $S$ 到顶点 $j$ 的最短路径所经过的顶点集合（包括 $S$ 和 $j$），以及从顶点 $T$ 到顶点 $j$ 的最短路径所经过的顶点集合（包括 $T$ 和 $j$），这两个集合中共同包含的顶点个数是多少？

输入按以下格式从标准输入读入。 > $N$ $S$ $T$ > $u_1$ $v_1$ > $\vdots$ > $u_{N-1}$ $v_{N-1}$

请输出 $N$ 行。 第 $i$ 行输出关于顶点 $i$ 问题的答案。

### 样例解释 1 在本输入样例中，$S = 1, T = 4$。 - 当 $j = 1$ 时 - $S$ 到 $j$ 的最短路径包含的顶点集合为 $\{1\}$。 - $T$ 到 $j$ 的最短路径包含的顶点集合为 $\{1, 2, 4\}$。 - 两个集合的交集只有顶点 $1$，所以答案为 $1$。 - 当 $j = 5$ 时 - $S$ 到 $j$ 的最短路径包含的顶点集合为 $\{1, 2, 3, 5\}$。 - $T$ 到 $j$ 的最短路径包含的顶点集合为 $\{2, 3, 4, 5\}$。 - 两个集合的交集为顶点 $2, 3, 5$，所以答案为 $3$。 ### 数据范围 - 所有输入均为整数 - $3 \leq N \leq 200,\!000$ - $1 \leq S, T \leq N$ - $S \neq T$ - $1 \leq u_i, v_i \leq N$ （$1 \leq i \leq N-1$） - 输入保证图是一棵树 由 ChatGPT 5 翻译