题目背景

2025 年 03 月 GESP C++ 六级编程第 1 题

题目描述

小 A 有一棵 $n$ 个结点的树，结点编号为 $1,2,ldots,n$。小 A 想在树上漫步：他可以从某个结点出发，每一步移动到相邻结点，并且只会在偶数步（可以是零步）后结束漫步。

对于树上的每个结点，请求出从该结点出发，经过偶数步能够结束漫步的结点数量。漫步过程中可以经过重复结点。

输入格式

第一行输入正整数 $n$。 接下来 $n-1$ 行，每行输入两个整数 $u_i,v_i$，表示树上的一条边。

输出格式

输出一行 $n$ 个整数。第 $i$ 个整数表示从结点 $i$ 出发、经过偶数步能够结束漫步的结点数量。

3
1 3
2 3

2 2 1

4
1 3
3 2
4 3

3 3 1 3

数据范围与提示

• 对于 $40\%$ 的测试点，保证 $1 \le n\le 10^3$。
• 对于全部测试点，保证 $1 \le n\le 2 imes 10^5$。

来源

GESP 2025 年 03 月 C++ 六级 T1