[题解] [IOI2008] Island

给出一个 $n$ 个点的基环树森林（每一个点有一条无向边），让你求出所有基环树的直径（即一条不经过重复点的基环树上的最长路径）之和。

$2\le n\le 10^6$

题目链接

---

思路

我们考虑不使用邻接表，而是只记录一个点的边的目标位置（ $tar_x$ ）和这条边的长度 （ $wei_x$ ）。

我们发现对于一个在环上的点 $x$，$tar_x$ 必定是这个环上的另一个点。而对于不在环上的点，它们必定构成一个树形结构，而且所有树的根的 $tar$ 必定是一个环上的点。很容易理解，不加说明。

下面，对于基环树环上的每个点 $x$ ，我们称不在环上 $tar$ 为 $x$ 的所有树和 $x$ 共同组成的集合为外环树（自己瞎造的名字）。举个例子：

这里的 1、2、3 都是环上的点。那么 1 的外环树就是 ${1,5,6,7,8}$，2 的外环树是 ${2}$ ，3 的外环树是 ${3,4}$。

我们记一个点 $x$ 的外环树的直径为 $g_x$ ，外环树上从 $x$ 开始的最长链的长度为 $f_x$。同样以上面那张图为例子，那么 $f_1$ 就是 7（3+4），$g_1$ 就是 8（4+1+3）。

我们发现，一个基环树的直径要不是一个外环树的直径，要不就是 $f_i$ +（$i \to j$）+ $f_j$ （ $i,j$ 都是环上的点）。

第二种情况可能不太好理解。以上图为例，$4\to 3\to 2\to 1\to 5\to 7$ 就属于是第二种情况。

那么接下来就简单了。我们只需要用拓扑序处理出每一个环上的点的 $f$ 和 $g$，然后再对于每一个环处理。我们从任意一个点开始，将整个环转换为一条链（比如上图中的环从 1 开始会变成 $[1,2,3]$ ，然后从左到右扫。我们注意到，对于两个点 $i$ 和 $j$（$i$ 在数组中的位置小于 $j$），$(i\to j)$ 事实上是可以选择两条不同的路径（如上图 $(1\to 2)$ 可以是 $1\to 2$ 或 $1\to 3\to 2$。因此我们令环上路径长度的前缀和为 $pre$，环的路径总长度为 $len$，再记（下面 $i$ 的下标小于 $j$）：
$$
\begin{aligned}
ret1&=\max{f_i+f_j+pre_j-pre_i}\
ret2&=\max{f_i+f_j+len-(pre_j-pre_i)}
\end{aligned}
$$
我们发现 $i$ 和 $j$ 的贡献在上面两个式子中是独立的，我们可以记一下当前下标小于 $j$ 的 所有 $i$ 中最大的 $f_i-pre_i$（ $m1$ ） 和 $f_i+pre_i$（ $m2$ ），然后每次新扫到一个点就可以用 $m1$ 和 $m2$ 更新。

那么最后的答案就是（$i$ 为环上的点）：
$$
ans=\max{ret1,ret2,g_i}
$$
对于每一个环扫一遍即可。

---

小优化：

• 我们再遍历完一个环之前并没法拿到这个环的长度 $len$，因此我们更新 $ret2$ 时不加上 $len$，最后遍历完后再给 $ret2$ 加上 $len$ 即可。

• 我们可以把 $g_i$ 顺便统计到 $ret1$ 里面，并没有什么用。

---

代码

494ms / 30.84MB，目前洛谷2nd最优解

mivik.h

// Mivik 2020.8.22
#include <mivik.h>

#include <algorithm>
#include <climits>

MI cin;

typedef long long qe;

const int nmax = 1000005;

template<typename T> inline bool gmax(T& a, const T& b) { return a < b && (a = b, true); }

int n;
int tar[nmax], wei[nmax];
// deg -> degree 度数
int deg[nmax];
qe f[nmax], g[nmax];
inline qe loop(int x) {
	const int beg = x;
	qe m1 = f[x], m2 = f[x];
	qe pre = wei[x];
	qe ret1 = g[x];
	x = tar[x];
	qe ret2 = LLONG_MIN;
	while (x != beg) {
		deg[x] = 0;
		gmax(ret1, f[x] + pre + m1);
		gmax(ret2, f[x] - pre + m2);
		gmax(ret1, g[x]);
		gmax(m1, f[x] - pre);
		gmax(m2, f[x] + pre);
		pre += wei[x];
		x = tar[x];
	}
	return std::max(ret1, ret2 + pre);
}
int main() {
	cin > n;
	for (int i = 1; i <= n; ++i) {
		cin > tar[i] > wei[i];
		++deg[tar[i]];
	}
	static int q[nmax];
	int head = 1, tail = 0;
	for (int i = 1; i <= n; ++i) if (!deg[i]) q[++tail] = i;
    // 计算出环上每个点的 f[i] 和 g[i]
	while (head <= tail) {
		const int x = q[head++];
		const qe cc = f[x] + wei[x];
		gmax(g[tar[x]], f[tar[x]] + cc);
		gmax(g[tar[x]], g[x]);
		gmax(f[tar[x]], cc);
		if (!(--deg[tar[x]])) q[++tail] = tar[x];
	}
	qe ans = 0;
	for (int i = 1; i <= n; ++i) // 如果 deg[i] 不为 0 代表 i 是在环上
    	if (deg[i]) ans += loop(i);
	cout < ans < endl;
}