#P12666. [KOI 2023 Round 2] 草地上的蚁穴

    ID: 14226 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2023树形 DP组合数学KOI(韩国)

[KOI 2023 Round 2] 草地上的蚁穴

题目背景

试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

KOI 公园的草地上,有一个蚂蚁们聚居的蚁穴。该蚁穴由 NN 个房间构成,并且存在恰好 N1N - 1 条通道,连接着不同的两个房间。你可以通过这些通道,从任意一个房间出发,到达任何其他房间。这意味着蚁穴构成了一棵由 NN 个节点组成的树。每个房间都被赋予了从 11NN 之间的唯一编号。

每个房间最多只能居住一只蚂蚁。如果两只蚂蚁分别居住在通过通道直接相连的两个房间中,它们会感到不舒服。因此,在当前蚁穴中,任何一条通道所连接的两个房间中,最多只能有一个房间居住蚂蚁。

蚂蚁们非常聪明,因此在上述条件允许的情况下,它们已经安排好了最多数量的蚂蚁居住在蚁穴中。换句话说,如果现在再试图增加一只蚂蚁进入蚁穴,不论怎么重新分配蚂蚁的位置,都无法满足上述条件。

在一个晴朗的夏日,KOI 公园迎来了大量前来野餐的游客。当游客们在草地上玩耍时,蚁穴的土壤有可能被踩松,于是某些原本未直接相连的两个房间之间可能会新形成一条通道。此时,新形成通道的两个房间可能原本就已经通过一条通道直接连接,也可能不相连。换句话说,对于任意两个整数 1i<jN1 \leq i < j \leq Nii 号房间和 jj 号房间之间都可能新建一条通道,无论这两者之间原本是否已有通道。

由于新通道的形成,某些本来不直接相连的、各自居住着蚂蚁的房间之间可能会变得直接相连,从而导致这两只蚂蚁感到不适。因此,居住在蚁穴中的蚂蚁们可能需要重新调整其分布,以重新满足上述限制条件。

根据选定的 (i,j)(i, j),这种重新调整有时是可能的,但有时则不行。某些情况下,不论怎样调整蚂蚁的位置,都无法使当前所有蚂蚁在新图结构中继续满足限制条件,这时候,部分蚂蚁可能不得不离开蚁穴。

若对于某一对整数 1i<jN1 \leq i < j \leq N,在 ii 号房间和 jj 号房间之间新建一条通道后,蚂蚁们可以通过适当的重新分布,在不驱逐任何一只蚂蚁的前提下继续满足限制条件,则称这对 (i,j)(i, j)和平的对

给定蚁穴的结构,请编程计算在所有可能的新通道对中,属于和平的对的数量。

输入格式

第一行输入一个整数 NN,表示房间的数量。
接下来的 N1N - 1 行中,每行输入两个整数 uuvv,表示 uu 号房间与 vv 号房间之间有一条通道连接。

输出格式

输出一个整数,表示在所有可能的新通道对中,属于和平的对的数量。

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 解释

最多可以安排 33 只蚂蚁,例如放在房间 {2,3,4}\{2, 3, 4\}。已经直接连接的房间对之间即使新建通道,也不影响原有安排。因此,这种情况共有 33 个和平的对。其余房间对间一旦建立通道,将无法维持当前蚂蚁数量。

样例 2 解释

最多可以安排 33 只蚂蚁,例如放在房间 {1,3,6}\{1, 3, 6\}。无论在哪两个房间之间新建通道,都能找到重新分配的方案使得 33 只蚂蚁依然满足条件,因此总共有 (62)=15\binom{6}{2} = 15 个和平的对。

限制条件

  • 所有输入均为整数。
  • 2N2500002 \leq N \leq 250\,000
  • 所有 u,vu, v 满足 1u,vN1 \leq u, v \leq Nuvu \ne v
  • 给定的蚁穴结构一定构成一棵树。

子任务

1.(8 分)N16N \leq 16
2.(6 分)N80N \leq 80
3.(18 分)N400N \leq 400
4.(18 分)N2000N \leq 2\,000
5.(6 分)N10000N \leq 10\,000
6.(8 分)N50000N \leq 50\,000
7.(36 分)无附加限制

翻译由 ChatGPT-4o 完成