你好！我是你的OI金牌教练。

我们已经练习了线性结构（数组、前缀和、差分、双指针、单调栈）。今天，我们把目光投向西周时期，结合**“分封制与宗法制”的历史背景，来攻克计算机科学中极其重要的一种非线性数据结构**——树 (Tree)。

这道题目符合 GESP 6级 难度，考察的是树的存储（邻接表）以及深度优先搜索 (DFS) 的应用，具体场景是计算子树大小 (Subtree Size)。

第一部分：背景知识讲解

1. 西周分封制 (The Feudal System of Western Zhou)

公元前1046年，周武王姬发在牧野之战中击败商纣王，建立周朝，定都镐京。为了巩固统治，周天子实行了“分封制”。

• 授民授疆土：周天子把土地和人民分封给宗亲和功臣，让他们建立诸侯国。
• 层级关系：周天子是最高统治者；诸侯在自己的封国内，又可以将土地分封给卿大夫；卿大夫再分封给士。这样就形成了“天子—诸侯—卿大夫—士”的金字塔式等级结构。

2. 树形结构 (Tree Structure)

在计算机科学中，这种“一对多”的层级关系完美对应了树这种数据结构。

• 根节点 (Root)：对应周天子（唯一的最高权力）。
• 父节点 (Parent) 与 子节点 (Child)：封君与封臣的关系。诸侯是天子的子节点，同时又是卿大夫的父节点。
• 子树 (Subtree)：以某个节点为根，囊括其所有后代节点的结构。

3. 算法痛点

如果周天子想知道，某位诸侯（及其下属所有层级）总共管理了多少人（或者多少个下级贵族），我们就需要统计树上以该节点为根的子树中节点的总数。

第二部分：题目内容

题目名称：周朝的等级 (The Hierarchy of Zhou)

题目描述

西周建立初期，周天子制定了严格的分封体系。我们将整个贵族群体看作一棵树。 全天下共有 $N$ 名贵族，编号为 $1$ 到 $N$。其中，编号为 $1$ 的是周天子（根节点）。

除了周天子之外，其他 $N-1$ 名贵族都有且仅有一位直接上级（父节点）。 为了便于管理，周天子想知道每一位贵族的势力范围。 一个贵族的“势力范围”定义为：他自己加上他所有直接或间接下属的总人数。 换句话说，对于树上的节点 $u$，你需要计算以 $u$ 为根的子树大小（包含 $u$ 自身）。

请你编写程序，根据给定的分封关系，计算并输出每一位贵族的势力范围。

输入格式

第一行包含一个正整数 $N$，表示贵族的总数。

接下来 $N-1$ 行，每行包含两个正整数 $u, v$，表示 $u$ 是 $v$ 的直接上级（即 $u$ 是 $v$ 的父节点）。 输入保证结构是一棵以 $1$ 为根的树。

输出格式

输出一行，包含 $N$ 个整数，第 $i$ 个整数表示编号为 $i$ 的贵族的势力范围（子树大小）。整数之间用空格隔开。

输入输出样例 #1

输入：

5
1 2
1 3
2 4
2 5

输出：

5 3 1 1 1

样例 #1 解释： 树的结构如下：

      1
     / \
    2   3
   / \
  4   5

• 贵族 1：下属有 2,3,4,5。加上自己，共 5 人。
• 贵族 2：下属有 4,5。加上自己，共 3 人。
• 贵族 3：无下属（叶子节点）。共 1 人。
• 贵族 4：无下属。共 1 人。
• 贵族 5：无下属。共 1 人。

输入输出样例 #2

输入：

6
1 2
2 3
3 4
4 5
5 6

输出：

6 5 4 3 2 1

样例 #2 解释： 这是一条链：$1 \to 2 \to 3 \to 4 \to 5 \to 6$。 1号管所有人(6)，2号管5个... 6号只管自己(1)。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 10^5$
• 保证是一棵合法的树，根节点为 1。