题目描述

你将要游览一个有N个岛屿的公园。从每一个岛i出发，只建造一座桥。桥的长度以Li表示。公园内总共有N座桥。尽管每座桥由一个岛连到另一个岛，但每座桥均可以双向行走。同时，每一对这样的岛屿，都有一艘专用的往来两岛之间的渡船。 相对于乘船而言，你更喜欢步行。你希望所经过的桥的总长度尽可能的长，但受到以下的限制。 • 可以自行挑选一个岛开始游览。 • 任何一个岛都不能游览一次以上。 • 无论任何时间你都可以由你现在所在的岛S去另一个你从未到过的岛D。由S到D可以有以下方法： o 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离；或者 o 渡船：你可以选择这种方法，仅当没有任何桥和/或以前使用过的渡船的组合可以由S走到D（当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛）。 注意，你不必游览所有的岛，也可能无法走完所有的桥。 任务 编写一个程序，给定N座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的最大长度。 限制 2 <= N <= 1,000,000 公园内的岛屿数目。 1<= Li <= 100,000,000 桥i的长度。

输入格式

• 第一行包含N个整数，即公园内岛屿的数目。岛屿由1到N编号。 • 随后的N行每一行用来表示一个岛。第i 行由两个以单空格分隔的整数，表示由岛i筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度Li。你可以假设对於每座桥，其端点总是位于不同的岛上。

输出格式

你的程序必须向标准输出写出包含一个整数的单一行，即可能的最大步行距离。 注1：对某些测试，答案可能无法放进32-bit整数，你要取得这道题的满分，可能需要用Pascal的int64或C/C++的long long类型。 注2：在比赛环境运行Pascal程序，由标准输入读入64-bit数据比32-bit数据要慢得多，即使被读取的数据可以32-bit表示。我们建议把输入数据读入到32-bit数据类型。 评分 N不会超过4,000。

---

题目的第二句话说明了这是一道基环树的题。我们可以按照基环树的套路来做。

我们定义一个东西叫做：基环树的直径。类似于树的直径，它可以理解为：基环树上距离最远的两个点之间的距离。那么直径显然有两种情况：

1.直径是以环上一点为根的子树的直径。

2.直径由环上某两点的子树的最长链加上环上最大距离组成。

为什么叫环上最大距离呢？因为题目是个无向图，所以我们可以顺时针走，也可以逆时针走。

考虑第一种情况

很容易做，直接树形dp或者搜索即可。这里我用的dfs。

考虑第二种情况

设以i为根的子树的最长链长度为dep(i)，我们可以列出答案的式子：

\[ ans=Max_{i{\in}loop,j{\in}loop,i{\neq}j}{\{}dep[i]+dep[j]+dist(i,j){\}} \]

最主要就是这个dist怎么算。我们可以用断环成链的技巧，从某个位置开始把环断开，并复制一段到后面去。然后我们计算出环上距离的前缀和sum数组。设环点数为len，那么:

\[ dist(i,j)=Max(sum[i]-sum[j],sum[j+len]-sum[i]); \]

当然我们不需要判断这个max，只需要从1枚举到2倍len即可。带入刚才的式子：

\[ ans=Max_{1≤i≤2*len,1≤j≤2*len,i{\neq}j}{\{}dep[i]+dep[j]+sum[i]-sum[j]{\}} \]

直接算就是O(N^2)的复杂度，显然过不了一百万的数据。考虑到答案式子的这个结构，我们可以想到一种优化：

单调队列优化。只需在枚举i的同时用单调队列维护一段长度为len的区间内dep(j)-sum(j)的最大值即可。

均摊下来复杂度就是O(N)。

*很久前写的代码，码风根现在不大像(我尽量改了一下代码)

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 1000005
using namespace std;
 
struct edge{
    int to, dis, next;
    edge(){}
    edge(const int &_to, const int &_dis, const int &_next){
        to = _to;
        dis = _dis;
        next = _next;
    }
}e[maxn << 1];
int head[maxn], k;
 
struct node{
    int to;
    long long w;
    node(){}
    node(const int &_to, const long long &_w){
        to = _to;
        w = _w;
    }
}fa[maxn], loop[maxn];
 
int vis[maxn], id, cnt;
long long sum[maxn << 1], dep[maxn << 1], mmax;
int is_c[maxn], now, pos;
int list[maxn << 1], l, r;
int n;
 
inline void add(const int &u, const int &v, const int &w){
    e[k] = edge(v, w, head[u]);
    head[u] = k++;
}
 
inline void get_loop(const int &u){
    vis[u] = ++id;
    int v;
    for(int i = head[u]; ~i; i = e[i].next){
        v = e[i].to;
        if(v == fa[u].to) continue;
        if(!vis[v]){
            fa[v] = node(u, e[i].dis);
            get_loop(v);
        }else{
            if(vis[v] < vis[u]) continue;
            loop[++cnt] = node(v, e[i].dis);
            for(; v != u; v = fa[v].to){
                loop[++cnt] = fa[v];
            }
        }
    }
}
 
inline void dfs(const int &u, const int pre, const long long &w){
    if(w >= mmax) mmax = w,pos = u;
     
    int v;
    for(int i = head[u]; ~i; i = e[i].next){
        v = e[i].to;
        if(v != pre && (!is_c[v] || v == now)) dfs(v, u, w + e[i].dis);
    }
}
 
inline long long f(const int &i){ return dep[i] - sum[i]; }
 
int main(){
    memset(head, -1, sizeof head);
    scanf("%d", &n);
    int v, w;
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &v, &w);
        add(i, v, w);
        add(v, i, w);
    }
     
    long long ans = 0, t;
    for(int i = 1; i <= n; i++) if(!vis[i]){
        cnt = id = t = 0;
        get_loop(i);
        for(int j = 1; j <= cnt; j++) is_c[loop[j].to] = true;
        for(int j = 1; j <= cnt; j++){
            mmax = 0,now = -1;
            dfs(loop[j].to, 0, 0);
            dep[j] = mmax;
             
            now = loop[j].to;
            dfs(pos, 0, 0);
            t = max(mmax, t);
        }
         
        for(int j = 1; j <= cnt; j++) dep[j + cnt] = dep[j];
        l = 1,r = 0;
        for(int j = 1; j <= cnt << 1; j++){
            if(j <= cnt) sum[j] = sum[j - 1] + loop[j].w;
            else sum[j] = sum[j - 1] + loop[j - cnt].w;
            if(l <= r) t = max(t, f(list[l]) + dep[j] + sum[j]);
            while(l <= r && f(list[r]) <= f(j)) r--;
            list[++r] = j;
            while(l <= r && list[l] <= j - cnt + 1) l++;
        }
        ans += t;
    }
     
    printf("%lld\n", ans);
    return 0;
}