33OJ
登录 注册

#P17743. [ICPC 2019 Xuzhou R] Kill the tree

[ICPC 2019 Xuzhou R] Kill the tree

题目描述

给定一棵有 NN 个顶点的树(顶点编号从 11 到 NN),其中 11 号顶点为树根。树上每条边的边权均为 11。

定义 d(u,v)d(u, v) 为顶点 uu 与 vv 之间的距离。

定义 c(w)=∑v∈Td(w,v)c(w)=\sum \limits_{v \in T} d(w, v)。如果树 TT 上的某个顶点 ww 满足 c(w)≤min⁡u∈Tc(u)c(w) \le \min \limits_{u \in T} c(u),则称 ww 为该树的 关键点。

现在,对于每个 i∈[1,N]i \in [1, N],你需要输出以顶点 ii 为根的子树的所有关键点。

输入格式

第一行包含一个整数 NN,表示树的顶点数。

接下来 N−1N - 1 行,第 ii 行包含两个整数 ai,bia_i, b_i,表示树上的第 ii 条边。

  • 1≤N≤2×1051 \le N \le 2 \times 10^5
  • 1≤ai,bi≤N1 \le a_i, b_i \le N
  • 输入保证构成一棵树

输出格式

输出 NN 行。

在第 ii 行,按升序输出以顶点 ii 为根的子树的所有关键点。同一行中的整数之间用一个空格分隔。

4
1 2
2 3
2 4
2
2
3
4

提示

翻译由 DeepSeek V4 Pro 完成