第 3 题 草地上的蚁穴 (lawnnest)

CSP-S 复赛模拟赛 22 · 时间限制 1.0 s · 空间限制 256 MB · 171 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 lawnnest.in，输出文件 lawnnest.out。

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

题目描述

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

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

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

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

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

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

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

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

输入格式

第一行输入一个整数 $N$，表示房间的数量。

接下来的 $N - 1$ 行中，每行输入两个整数 $u$ 和 $v$，表示 $u$ 号房间与 $v$ 号房间之间有一条通道连接。

输出格式

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

样例

样例 1

输入：

4
1 2
1 3
1 4

输出：

3

样例 2

输入：

6
1 2
2 3
3 4
4 5
5 6

输出：

15

样例 3

输入：

7
1 2
1 3
2 4
2 5
3 6
3 7

输出：

11

提示

样例 1 解释

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

样例 2 解释

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

限制条件

• 所有输入均为整数。
• $2 \le N \le 250\,000$
• 所有 $u, v$ 满足 $1 \le u, v \le N$ 且 $u \neq v$
• 给定的蚁穴结构一定构成一棵树。

子任务

1. （8 分）$N \le 16$
2. （6 分）$N \le 80$
3. （18 分）$N \le 400$
4. （18 分）$N \le 2\,000$
5. （6 分）$N \le 10\,000$
6. （8 分）$N \le 50\,000$
7. （36 分）无附加限制

翻译由 ChatGPT-4o 完成