ACAC 题库 ac.isam.top
GitHub
欧姆龙编程竞赛 2026（第 479 场 AtCoder Beginner Contest）
E
切断与累加
Cut and Add
AtCoder
⌀ 1000
原题
← DF →

切断与累加AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

There is a tree with $N$ vertices numbered $1,2,\dots,N$. Here, $N$ is odd. The edges are also numbered $1,2,\dots,N-1$, and edge $i$ connects vertices $A_i$ and $B_i$.

有一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\dots,N$。其中，$N$ 为奇数。 边的编号为 $1,2,\dots,N-1$，边 $i$ 连接顶点 $A_i$ 和 $B_i$。AI (CI翻译)

Each vertex $i$ has a variable $x_i$, and initially $x_i=0$ for every vertex $i$.

每个顶点 $i$ 都有一个变量 $x_i$，初始时，所有顶点 $i$ 的变量均满足 $x_i=0$。AI (CI翻译)

Now, for $i=1,2,\dots,N-1$ in this order, perform the following operation.

现在，按照 $i=1,2,\dots,N-1$ 的顺序执行以下操作。AI (CI翻译)

  • First, remove edge $i$. As a result, the tree is split into two connected components.
  • For every vertex $v$ in the connected component containing more vertices, add $i$ to $x_v$.
  • Since $N$ is odd, the connected component containing more vertices is uniquely determined.
  • Finally, restore edge $i$.
  • 首先，删除边 $i$。此时，树被分成两个连通分量。
  • 对于顶点数较多的连通分量中的每个顶点 $v$，将 $x_v$ 加上 $i$。
  • 由于 $N$ 为奇数，顶点数较多的连通分量可以唯一确定。
  • 最后，恢复边 $i$。
AI (CI翻译)

Find the values of the variables $x_1,x_2,\dots,x_N$ of the vertices after all operations are performed.

求所有操作完成后，各顶点的变量 $x_1,x_2,\dots,x_N$ 的值。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • All input values are integers.
  • $N$ is an odd number satisfying $3 \le N \le 2 \times 10^5 - 1$.
  • $1 \le A_i < B_i \le N$
  • The given graph is a tree.
  • 所有输入值均为整数。
  • $N$ 为奇数，且满足 $3 \le N \le 2 \times 10^5 - 1$。
  • $1 \le A_i < B_i \le N$
  • 给定的图是一棵树。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入通过标准输入以如下格式给出：AI (CI翻译)

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the final values of the variables in the following format:

按如下格式输出各变量的最终值：AI (CI翻译)

x_1 x_2 \dots x_N

x_1 x_2 \dots x_N
AI (CI翻译)

样例

Input #1
5
2 4
1 5
1 4
1 3
Output #1
10 6 6 7 8
- For $i=1$, the following operation is performed. - Removing edge $1$ splits the tree into a connected component with vertex $2$ and a connected component with vertices $1,3,4,5$. - The larger one is the connected component with vertices $1,3,4,5$, so $1$ is added to all of their variables. - As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(1,0,1,1,1)$. - Finally, edge $1$ is restored. - For $i=2$, the following operation is performed. - Removing edge $2$ splits the tree into a connected component with vertex $5$ and a connected component with vertices $1,2,3,4$. - The larger one is the connected component with vertices $1,2,3,4$, so $2$ is added to all of their variables. - As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(3,2,3,3,1)$. - Finally, edge $2$ is restored. - For $i=3$, the following operation is performed. - Removing edge $3$ splits the tree into a connected component with vertices $2,4$ and a connected component with vertices $1,3,5$. - The larger one is the connected component with vertices $1,3,5$, so $3$ is added to all of their variables. - As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(6,2,6,3,4)$. - Finally, edge $3$ is restored. - For $i=4$, the following operation is performed. - Removing edge $4$ splits the tree into a connected component with vertex $3$ and a connected component with vertices $1,2,4,5$. - The larger one is the connected component with vertices $1,2,4,5$, so $4$ is added to all of their variables. - As a result, the values of the variables become $(x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8)$. - Finally, edge $4$ is restored. The final values of the variables are $(x_1,x_2,x_3,x_4,x_5)=(10,6,6,7,8)$.
Input #2
3
1 2
2 3
Output #2
2 3 1
Input #3
9
4 6
2 3
1 5
7 8
2 9
5 6
2 6
7 9
Output #3
20 36 34 28 23 29 23 19 31
题目信息
题号
abc479_e
所属比赛
欧姆龙编程竞赛 2026（第 479 场 AtCoder Beginner Contest）
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。