狐狸二郎和其他动物在茂密的森林里快乐地生活、玩耍。
森林里有很多动物的游乐场,游乐场之间有几条小路相连。当然,您可以通过多条路径从任何一个游乐场到另一个游乐场,并且从一个游乐场到另一个游乐场只有一条路径。
然而,动物们的快乐时光并没有持续多久。人类突然开始进入森林并破坏动物的游乐场。
当某个游乐场被人类破坏时,动物通过就会很危险。如果发生这种情况,动物的游乐场将会被分割,并且会出现无法从一个游乐场进入的游乐场。
二郎和其他动物想以某种方式抵抗这一点,但不幸的是他们无法用他们的力量阻止人类。
由于别无选择,动物们决定前往划分的游戏区域中可能保持最长的部分。
我为动物感到难过,但人类对森林的破坏没有停止的迹象。至少,我希望您能帮助这些动物,让它们能够在更多的游乐场里尽可能长时间地玩耍。
課題
N 我们有一棵由顶点组成的树。在每个顶点 0 如果要将其更改为输出最多为 N-1 它们用不同的整数编号,最大为 。
执行以下程序:
-
具有以下参数的过程 初始化(N,E):
- N -- 顶点数。在顶部 0 如果要将其更改为输出最多为 N-1 它们用不同的整数编号,最大为 。
- E -- 表示边缘信息的二维整数数组。0 ≤ i < N-1 对于 ,边缘 i 是两个不同的顶点 E[i][0] 和 将其放在 E[i][1] 是平局。E 保证表示树结构。换句话说,从任何一个顶点到任何其他顶点都可以追踪一条边,并且只有一条路径。
-
具有以下参数的过程 查询(i)
在调用:
- i -- 要销毁的顶点数。
例
例1

図 1
如图1所示 N = 5,
| E = 考虑 |
|
一、流程 初始化 使用上述参数调用 。然后是程序 每次破坏都会调用一次 查询 。以下是调用和正确返回值的示例:
| 破壊 | 参数 | 返回值 |
|---|---|---|
| 1 | 查询(1) | 3 |
| 2 | 查询(0) | 3 |
| 3 | 查询(3) | 1 |
| 4 | 查询(4) | 1 |
例2

図 2
如图2所示 N = 5,
| E = 考虑 |
|
一、流程 初始化 使用上述参数调用 。然后是程序 每次破坏都会调用一次 查询 。以下是调用和正确返回值的示例:
| 破壊 | 参数 | 返回值 |
|---|---|---|
| 1 | 查询(1) | 4 |
| 2 | 查询(2) | 3 |
| 3 | 查询(0) | 1 |
| 4 | 查询(4) | 1 |
小課題
小課題 1 (20 点)
- 1 ≤ N ≤ 1 000
小課題 2 (25 点)
- (仅适用于这个小作业) 树处于一条直线上。
即所有 关于 i 关于 E[i][0] = i, E[i][1] = i+1 成立。 - 1 ≤ N ≤ 100 000
小課題 3 (55 点)
- 1 ≤ N ≤ 100 000
实施细节
制限
- CPU时间限制:2秒
- 内存限制:64 MB
注意: 堆栈的大小没有固定限制。作为堆栈使用的内存包含在总内存使用量中。
接口 (API)
- 实现文件夹:animals/(原型: 动物.zip)
- 参赛者实现的文件:animals.cpp
- 提交文件接口:animals.h
- 评分程序示例:grader.cpp
- 评分程序的示例输入:grader.in.1、grader.in.2、...
注意:示例评分程序按以下格式读取输入。- 1 行目: N
- 从第 2 行开始 对于 N 行目: 0 ≤ i < N-1 对于 ,i+2 在线 E[i][0] 和 将其放在 E[i][1] 用空格分隔。
- N+1 行目: N-1 它们用不同的整数编号,最大为 整数 我[0], 我[1], ..., 我[N-2] 用空格分隔。我[i] 是 i 这是要销毁的顶点的编号。
- 评分器输入样本的预期输出:grader.expect.1、grader.expect.2、...
注意:示例评分程序按以下格式写入输出。- 1行目: N-1 它们用不同的整数编号,最大为 整数 X[0], X[1], ..., X[N-2] 是用空格分隔的输出。X[i] 是 i 第 查询 这是调用时应该返回的返回值。