一、题目

Description
你将要游览一个有N个岛屿的公园。从每一个岛i出发，只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛，但每座桥均可以双向行走。同时，每一对这样的岛屿，都有一艘专用的往来两岛之间的渡船。 相对于乘船而言，你更喜欢步行。你希望所经过的桥的总长度尽可能的长，但受到以下的限制。
• 可以自行挑选一个岛开始游览。 • 任何一个岛都不能游览一次以上。 • 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。由S到D可以有以下方法： o 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离；或者 o 渡船：你可以选择这种方法，仅当没有任何桥和/或以前使用过的渡船的组合可以由S走到D（当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。 注意，你不必游览所有的岛，也可能无法走完所有的桥。 任务 编写一个程序，给定N座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。 限制 2 <= N <= 1,000,000 公园内的岛屿数目。 1<= Li <= 100,000,000 桥i的长度。
Input
• 第一行包含N个整数，即公园内岛屿的数目。岛屿由1到N编号。 • 随后的N行每一行用来表示一个岛。第i 行由两个以单空格分隔的整数，表示由岛i筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度Li。你可以假设对於每座桥，其端点总是位于不同的岛上。
Output
你的程序必须向标准输出写出包含一个整数的单一行，即可能的最大步行距离。 注1：对某些测试，答案可能无法放进32-bit整数，你要取得这道题的满分，可能需要用Pascal的int64或C/C++的long long类型。 注2：在比赛环境运行Pascal程序，由标准输入读入64-bit数据比32-bit数据要慢得多，即使被读取的数据可以32-bit表示。我们建议把输入数据读入到32-bit数据类型。 评分 N不会超过4,000。
Sample Input
7
3 8
7 2
4 2
1 4
1 9
3 4
2 3
Sample Output
24

二、题目的理解

其实所有岛屿构成一个基环树森林。至于为什么，每个图由\(m\)个点\(m\)条边组成，而他又是联通的。所以每个图都是基环树。

三、关于基环树

它是一棵树再连一条边形成的。所以它一般长成这样。

一般的处理方法都是把环找出来，树的管树的，再通过环上的合并。
我这里正好有一个扣环的代码。

void getloop(int u) {
    dfn[u] = ++timer;
    for (int e = fir[u]; e && !lpcnt; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v == pre[u]) continue;
        if (dfn[v]) {
            if (dfn[v] < dfn[u]) continue;
            for (int i = v; i != u; i = pre[i]) {
                lop[++lpcnt] = i;
                inl[i] = true;
            }
            lop[++lpcnt] = i;
            inl[u] = true;
            return;
        }
        pre[v] = u;
        getloop(v);
    }
}

这个代码是在\(u\)即根的时候判的环（可处理2元环）

四、基环树的直径

这个直径可能有两种情况
1、只位于一颗树内
2、两条树的最长链通过环连接
关于树的直径，不提。
关于第二种情况。
设环上的点的数目为\(m\)，设\(sum_i\)为编号为\(i\)的点到编号为\(1\)的点（都是环上的）的距离，设\(f_i\)为编号为\(i\)的树的最长至根的链（同样都是环上的）。我们设所有在环上走的方向均为顺时针，至于逆时针走更远的情况，只要把原数组复制一遍。对于一个点\(i\)只有前\(m-1\)个点可以转移至它。转移方程：\(ans_i=max(sum_i-sum_j+f_i+f_j)\)，即为：\(ans_i=max(f_j-sum_j)+sum_i+f_i\)，这个东西可以用滑动窗口解决。

五、代码

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#define fi first
#define se second
using namespace std;
typedef long long LL;
const LL INF = 1e15;
const int MAXN = 1000000;
struct Edge {
    int to, nxt, w;
} edge[MAXN + 5 << 1];
bool inl[MAXN + 5];
int ecnt, fir[MAXN + 5], pre[MAXN + 5], dfn[MAXN + 5], timer, n, lpcnt, eid[MAXN + 5], que[MAXN + 5];
pair <int, int> lop[MAXN + 5];
LL sum[MAXN + 5 << 1], ans, mxdis[MAXN + 5], ret;
template <typename T> void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { x = x * 10 + c - 48; c = getchar(); }
    x *= f;
}
void addedge(int u, int v, int w) {
    edge[++ecnt].to = v;
    edge[ecnt].nxt = fir[u];
    edge[ecnt].w = w;
    fir[u] = ecnt;
}
void getloop(int u) {
    dfn[u] = ++timer;
    for (int e = fir[u]; e && !lpcnt; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v == pre[u]) continue;
        if (dfn[v]) {
            if (dfn[v] < dfn[u]) continue;
            for (int i = v; i != u; i = pre[i]) {
                lop[++lpcnt] = make_pair(i, edge[eid[i]].w);
                inl[i] = true;
            }
            lop[++lpcnt] = make_pair(u, edge[e].w);
            inl[u] = true;
            return;
        }
        pre[v] = u;
        eid[v] = e;
        getloop(v);
    }
}                           //找环并计算距离
void dfs(int u, int fa) {
    mxdis[u] = 0;
    LL minx = 0, maxx = 0;
    for (int e = fir[u]; e; e = edge[e].nxt) {
        int v = edge[e].to;
        if (v == fa || inl[v]) continue;
        dfs(v, u);
        mxdis[u] = max(mxdis[u], mxdis[v] + edge[e].w);
        if (mxdis[v] + edge[e].w > maxx) {
            minx = maxx;
            maxx = mxdis[v] + edge[e].w;
        } else if (mxdis[v] + edge[e].w > minx)
            minx = mxdis[v] + edge[e].w;
    }
    ans = max(ans, minx + maxx);            //求出f[i]，并统计第一种情况
}
int main() {
    read(n);
    for (int u = 1; u <= n; ++u) {
        int v, w;
        read(v), read(w);
        addedge(u, v, w);
        addedge(v, u, w);
    }
    for (int u = 1; u <= n; ++u)
        if (!dfn[u]) {
            lpcnt = 0;
            getloop(u);
            ans = 0;
            for (int i = 1; i <= lpcnt; ++i) {
                dfs(lop[i].fi, 0);
                lop[lpcnt + i] = lop[i];
            }                   //复制一遍
            int head = 1, tail = 1;
            que[1] = 1;
            for (int i = 2; i <= lpcnt << 1; ++i) {
                while (head <= tail && i - que[head] >= lpcnt) ++head;  //去掉距离远的
                sum[i] = sum[i - 1] + lop[i - 1].se;
                ans = max(ans, mxdis[lop[i].fi] + sum[i] + mxdis[lop[que[head]].fi] - sum[que[head]]);
                while (head <= tail && mxdis[lop[que[tail]].fi] - sum[que[tail]] <= mxdis[lop[i].fi] - sum[i]) --tail;  //维护最优解
                que[++tail] = i;
            }
            ret += ans;
        }
    printf("%lld\n", ret);
    return 0;
}