参考《算法竞赛进阶指南》、AcWing题库

基环树

众所周知, $N$ 个点的树有 $N-1$ 条边。若在树上任意添加一条边, 则会形成一个环。除了环之外, 其余部分由若干棵子树构成。

我们把这种 $N$ 个点 $N$ 条边的连通无向图, 即在树上加一条边构成的恰好包含一个环的图, 称为 “基环树” 。如果不保证连通, 那么 $N$ 个点 $N$ 条边的无向图也可能是若干棵基环树组成的森林, 简称为 “基环树森林”。

在有向图中, 我们也有类似的概念。 $N$ 个点、 $N$ 条边、每个节点有且仅有一条入边的有向图就好像以 “基环” 为中心, 有向外扩展的趋势, 故称为 “外向树”。 $N$ 个点、 $N$ 条边、每个节点有且仅有一条出边的有向连通图就好像以 “基环” 为中心, 有向内收缩的趋势, 故称为 “内向树”。外向树和内向树也经常统称为 “基环树” 。如果不保证连通, 那么 $N$ 个点、 $N$ 条边、每个节点有且仅有一条出 (入) 边的有向图也可能是 “内 (外) 向树森林” 的形态。

基环树的结构仍然很简单, 但比树要复杂些, 因此常作为一些经典模型的扩展, 以适当增加题目的难度。例如基环树的直径、基环树两点之间的距离、基环树动态规划等。无论哪种模型, 求解基环树相关问题的方法一般都是先找出图中唯一的环, 把环作为基环树的广义 “根节点”, 把除了环之外的部分按照若干棵树处理, 再考虑与环一起计算。

例题

358. 岛屿

你准备游览一个公园，该公园由 $N$ 个岛屿组成，当地管理部门从每个岛屿出发向另外一个岛屿建了一座桥，不过桥是可以双向行走的。

同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。

相对于乘船而言，你更喜欢步行。

你希望所经过的桥的总长度尽可能的长，但受到以下的限制：

可以自行挑选一个岛开始游览。
任何一个岛都不能游览一次以上。
无论任何时间你都可以由你现在所在的岛 $S$ 去另一个你从未到过的岛 $D$ 。由 $S$ 到 $D$ 可以有以下方法：
（1）步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
（2）渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 $S$ 走到 $D$ （当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 $N$ 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。

输入格式

第 $1$ 行包含整数 $N$ 。

第 $2.. N+1$ 行，每行包含两个整数 $a$ 和 $L$ ，第 $i+1$ 行表示岛屿 $i$ 上建了一座通向岛屿 $a$ 的桥，桥的长度为 $L$ 。

输出格式

输出一个整数，表示结果。

对某些测试，答案可能无法放进 $32-bit$ 整数。

数据范围

$2 \le N \le 10^6$ ,
$1 \le L \le 10^8$

输入样例：

输出样例：

算法分析

Solution

359. 创世纪

上帝手中有 $N$ 种世界元素，每种元素可以限制另外 $1$ 种元素，把第 $i$ 种世界元素能够限制的那种世界元素记为 $A[i]$ 。

现在，上帝要把它们中的一部分投放到一个新的空间中去建造世界。

为了世界的和平与安宁，上帝希望所有被投放的世界元素都有至少一个没有被投放的世界元素限制它。

上帝希望知道，在此前提下，他最多可以投放多少种世界元素？

输入格式

第一行是一个整数 $N$ ，表示世界元素的数目。

第二行有 $N$ 个整数 $A[1], A[2], …, A[N]$ 。 $A[i]$ 表示第 $i$ 个世界元素能够限制的世界元素的编号。

输出格式

一个整数，表示最多可以投放的世界元素的数目。

数据范围

$N \le 10^6,1 \le A[i] \le N$

输入样例：

1 2	6 2 3 1 3 6 5

输出样例：

算法分析

Solution

360. Freda的传呼机

为了随时与 rainbow 快速交流，Freda 制造了两部传呼机。

Freda 和 rainbow 所在的地方有 $N$ 座房屋、 $M$ 条双向光缆。

每条光缆连接两座房屋，传呼机发出的信号只能沿着光缆传递，并且传呼机的信号从光缆的其中一端传递到另一端需要花费 $t$ 单位时间。

现在 Freda 要进行 $Q$ 次试验，每次选取两座房屋，并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。

$N$ 座房屋通过光缆一定是连通的，并且这 $M$ 条光缆有以下三类连接情况：

$A$ ：光缆不形成环，也就是光缆仅有 $N-1$ 条。
$B$ ：光缆只形成一个环，也就是光缆仅有 $N$ 条。
$C$ ：每条光缆仅在一个环中。

请你帮帮他们。

输入格式

第一行包含三个用空格隔开的整数， $N、M$ 和 $Q$ 。

接下来 $M$ 行每行三个整数 $x、y、t$ ，表示房屋 $x$ 和 $y$ 之间有一条传递时间为 $t$ 的光缆。

最后 $Q$ 行每行两个整数 $x、y$ ，表示 Freda 想知道在 $x$ 和 $y$ 之间传呼最少需要多长时间。

输出格式

输出 $Q$ 行，每行一个整数，表示 Freda 每次试验的结果。

数据范围

$2 \le N \le 10000$ ,
$N-1 \le M \le 12000$ ,
$Q = 10000$ ,
$1 \le x,y \le N$ ,
$1 \le t < 32768$

输入样例：

输出样例：

1
2

3
1