← 返回题目列表

AtCoder · ijpc_animals

A. 无辜动物与森林破坏

中文机器翻译题面 查看原题

狐狸二郎和其他动物在茂密的森林里快乐地生活、​​玩耍。

森林里有很多动物的游乐场,游乐场之间有几条小路相连。当然,您可以通过多条路径从任何一个游乐场到另一个游乐场,并且从一个游乐场到另一个游乐场只有一条路径。

然而,动物们的快乐时光并没有持续多久。人类突然开始进入森林并破坏动物的游乐场。

当某个游乐场被人类破坏时,动物通过就会很危险。如果发生这种情况,动物的游乐场将会被分割,并且会出现无法从一个游乐场进入的游乐场。

二郎和其他动物想以某种方式抵抗这一点,但不幸的是他们无法用他们的力量阻止人类。

由于别无选择,动物们决定前往划分的游戏区域中可能保持最长的部分。

我为动物感到难过,但人类对森林的破坏没有停止的迹象。至少,我希望您能帮助这些动物,让它们能够在更多的游乐场里尽可能长时间地玩耍。

課題

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) 在调用:
    • i -- 要销毁的顶点数。
    这个程序只是 已致电 N-1 它们用不同的整数编号,最大为 次。一次调用会破坏一个顶点(此破坏发生在所有先前的破坏之后)。已经破坏的顶点 i 不再指定。某个顶点 当销毁 i 时,它的顶点和所有连接到它的边都将被删除。每次调用都会调用森林(一棵或多棵树的集合)中的每棵树,这些森林在森林被破坏后仍然存在。最大顶点数 必须返回。返回所有现有树的最大顶点数(无论它们何时被分割)。

例

例1

図1
図 1

如图1所示 N = 5,

E = 考虑
0 1
1 2
2 3
3 4
的情况。

一、流程 初始化 使用上述参数调用 。然后是程序 每次破坏都会调用一次 查询 。以下是调用和正确返回值的示例:

破壊 参数 返回值
1 查询(1) 3
2 查询(0) 3
3 查询(3) 1
4 查询(4) 1

例2

図2
図 2

如图2所示 N = 5,

E = 考虑
2 1
0 2
4 0
3 0
的情况。

一、流程 初始化 使用上述参数调用 。然后是程序 每次破坏都会调用一次 查询 。以下是调用和正确返回值的示例:

破壊 参数 返回值
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 第 查询 这是调用时应该返回的返回值。