#P12666. [KOI 2023 Round 2] 草地上的蚁穴
[KOI 2023 Round 2] 草地上的蚁穴
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
KOI 公园的草地上,有一个蚂蚁们聚居的蚁穴。该蚁穴由 个房间构成,并且存在恰好 条通道,连接着不同的两个房间。你可以通过这些通道,从任意一个房间出发,到达任何其他房间。这意味着蚁穴构成了一棵由 个节点组成的树。每个房间都被赋予了从 到 之间的唯一编号。
每个房间最多只能居住一只蚂蚁。如果两只蚂蚁分别居住在通过通道直接相连的两个房间中,它们会感到不舒服。因此,在当前蚁穴中,任何一条通道所连接的两个房间中,最多只能有一个房间居住蚂蚁。
蚂蚁们非常聪明,因此在上述条件允许的情况下,它们已经安排好了最多数量的蚂蚁居住在蚁穴中。换句话说,如果现在再试图增加一只蚂蚁进入蚁穴,不论怎么重新分配蚂蚁的位置,都无法满足上述条件。
在一个晴朗的夏日,KOI 公园迎来了大量前来野餐的游客。当游客们在草地上玩耍时,蚁穴的土壤有可能被踩松,于是某些原本未直接相连的两个房间之间可能会新形成一条通道。此时,新形成通道的两个房间可能原本就已经通过一条通道直接连接,也可能不相连。换句话说,对于任意两个整数 , 号房间和 号房间之间都可能新建一条通道,无论这两者之间原本是否已有通道。
由于新通道的形成,某些本来不直接相连的、各自居住着蚂蚁的房间之间可能会变得直接相连,从而导致这两只蚂蚁感到不适。因此,居住在蚁穴中的蚂蚁们可能需要重新调整其分布,以重新满足上述限制条件。
根据选定的 ,这种重新调整有时是可能的,但有时则不行。某些情况下,不论怎样调整蚂蚁的位置,都无法使当前所有蚂蚁在新图结构中继续满足限制条件,这时候,部分蚂蚁可能不得不离开蚁穴。
若对于某一对整数 ,在 号房间和 号房间之间新建一条通道后,蚂蚁们可以通过适当的重新分布,在不驱逐任何一只蚂蚁的前提下继续满足限制条件,则称这对 为和平的对。
给定蚁穴的结构,请编程计算在所有可能的新通道对中,属于和平的对的数量。
输入格式
第一行输入一个整数 ,表示房间的数量。
接下来的 行中,每行输入两个整数 和 ,表示 号房间与 号房间之间有一条通道连接。
输出格式
输出一个整数,表示在所有可能的新通道对中,属于和平的对的数量。
4
1 2
1 3
1 4
3
6
1 2
2 3
3 4
4 5
5 6
15
7
1 2
1 3
2 4
2 5
3 6
3 7
11
提示
样例 1 解释
最多可以安排 只蚂蚁,例如放在房间 。已经直接连接的房间对之间即使新建通道,也不影响原有安排。因此,这种情况共有 个和平的对。其余房间对间一旦建立通道,将无法维持当前蚂蚁数量。
样例 2 解释
最多可以安排 只蚂蚁,例如放在房间 。无论在哪两个房间之间新建通道,都能找到重新分配的方案使得 只蚂蚁依然满足条件,因此总共有 个和平的对。
限制条件
- 所有输入均为整数。
- 所有 满足 且
- 给定的蚁穴结构一定构成一棵树。
子任务
1.(8 分)
2.(6 分)
3.(18 分)
4.(18 分)
5.(6 分)
6.(8 分)
7.(36 分)无附加限制
翻译由 ChatGPT-4o 完成