岛屿 / Island
题目链接：ybt金牌导航1-3-5 / luogu P4381
题目大意
有 n 个点 n 条边，边有边权，是双向的。
一条边只能走一次，一个点也只能经过一次。
如果两个点之间无法通过边连通，那你就可以选择渡船过，渡船之后它就相当于你走过的长度为 0 的边。
然后你可以自定起点，问你最多能走的距离。
思路
我们首先会发现是 n 个点 n 条边。
然后图其实就是由几个连通块组成，每个连通块都是有且只有一个环的情况。
那就是一个环，然后点可能会衍生出一些树。这种图其实就是叫做基环树。
那你根据题意，其实就是你要在每个基环树上找一条最长的路径（不能重复走），然后走完这一条就渡船到下一个基环树继续走。
而那个最长的路径就是基环树的直径。
那现在问题就变成了给你一个基环树，求它的直径。
那我们会想到这个直径有两种情况，要么经过环，要么不经过环。
那首先不经过环，那就只是在环上某个点衍生出来的树上找一条直径。
那可以想到用树形 DP 来解决，那就直接枚举环上每个点做一次就可以。
那如果经过环，那就要枚举两个点，然后它们到它们子树最远的位置和它们之间最远位置的和就是距离。
那你看到枚举两个点会超时，我们考虑弄出式子看如果优化。
首先它是环，你考虑破环为链。
然后你就会想到这么一个搞法，就是找到一个两个之间位置差距小于环大小的两个链上的点，然后让它的值最大。
点到它子树最远的距离 (d_i) 可以在第一种情况 DP 的时候算出，然后在环上的距离可以通过前缀和求出，因为你破了环，就相当于有两组距离小于环大小的点是表示这两组点的，然后距离就是从不同的方向，所以你在这两个间取了最大值就相当于用了环上距离远的那个。
（这里求距离你可以在链上搞一个前缀和 (s_i)，然后 (i,j(i<j)) 间距离就是 (s_j-s_i)）
那我们就是样让 (d_i+d_j+s_j-s_i) 最大，那把 (i,j) 的放在一起，让 (d_i-s_i+d_j+s_j) 最大，那我们枚举 (j)，那就是找 (i<j) 且 (j-ileq size)，使得 (d_i-s_i) 最大。（(size) 为环的大小）
你会发现它是可以单调队列优化的。
如果有一个点 (x)，有一个点 (y(x>y)) 满足 (d_y-s_yleq d_x-s_x)，那 (y) 就是没用的。
那就可以用这样的方法单调队列优化。
然后最后在这两种情况里面选一个最大值，就是这个基环树的贡献了。
把每个基环树的贡献加在一起，就是这个基环树森林的贡献，就是答案了。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
struct node {
ll x;
int to, nxt;
}e[2000001];
int n, le[1000001], KK;
int y, ltk[1000001], size;
int cir[1000001], fa[1000001];
ll z, dis[1000001], dp[1000001];
bool in[1000001];
ll sum[2000001], que[2000001];
void add(int x, int y, ll z) {
e[++KK] = (node){z, y, le[x]}; le[x] = KK;
}
void dfs(int now) {
ltk[now] = ++ltk[0];
for (int i = le[now]; i; i = e[i].nxt)
if (e[i].to != fa[now]) {
if (!ltk[e[i].to]) fa[e[i].to] = now, dfs(e[i].to);
else if (ltk[e[i].to] > ltk[now]) {
cir[++size] = e[i].to;
in[cir[size]] = 1;
for (int x = e[i].to; x != now; x = fa[x])
cir[++size] = fa[x], in[cir[size]] = 1;;
}
}
}
ll tree_dp(int root) {
ll re = 0;
in[root] = 1;
for (int i = le[root]; i; i = e[i].nxt)
if (!in[e[i].to]) {
re = max(re, tree_dp(e[i].to));
re = max(re, dp[e[i].to] + dp[root] + e[i].x);
dp[root] = max(dp[root], dp[e[i].to] + e[i].x);
}
return re;
}
ll work(int root) {
size = 0;
ltk[0] = 0;
dfs(root);
ll ans1 = 0, ans2 = 0;
cir[0] = cir[size];
for (int i = 1; i <= size; i++)
ans1 = max(ans1, tree_dp(cir[i]));
if (size == 2) {
for (int i = le[cir[1]]; i; i = e[i].nxt)
if (e[i].to == cir[2]) {
ans2 = max(ans2, dp[cir[1]] + dp[cir[2]] + e[i].x);
}
}
else {
for (int i = 1; i <= size; i++) {
for (int j = le[cir[i]]; j; j = e[j].nxt)
if (e[j].to == cir[i - 1]) {
sum[i] = sum[i - 1] + e[j].x;
break;
}
}
for (int i = 1; i < size; i++)
sum[i + size] = sum[size] + sum[i];
int l = 1, r = 1;
que[1] = 0;
for (int i = 1; i < (size << 1); i++) {
if (l <= r && que[l] <= i - size) l++;
ans2 = max(ans2, dp[cir[que[l] % size]] + dp[cir[i % size]] + sum[i] - sum[que[l]]);
while (l <= r && sum[que[r]] - dp[cir[que[r] % size]] >= sum[i] - dp[cir[i % size]]) r--;
que[++r] = i;
}
}
return max(ans1, ans2);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %lld", &y, &z);
add(i, y, z);
add(y, i, z);
}
ll ans = 0;
for (int i = 1; i <= n; i++)
if (!in[i]) {
ans += work(i);
}
printf("%lld", ans);
return 0;
}