BZOJ [Ioi2008]Island 岛屿

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

HINT

可以看出来这道题很难
可以看出来这道题在洛谷是黑题
可以看出来这是一道基环树
可以看出来可以DP
可以看出来很难写
可以看出来我的代码很好懂
算法：基环树+拓扑+单调队列、环形DP

/**************************************************************
    Problem: 1791
    User: wiiind
    Language: C++
    Result: Accepted
    Time:9996 ms
    Memory:103904 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
int n;
const int maxn=1000001;
int bel[maxn];
int head[maxn],nex[maxn<<1],to[maxn<<1],val[maxn<<1];
int cnt=0;
template < class T > inline void read (T &x){
    x=0;char ch=getchar();
    while(!isdigit(ch)){ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
}
inline void add (int x,int y,int z){
    nex[++cnt]=head[x];
    to[cnt]=y;
    val[cnt]=z;
    head[x]=cnt;
}
int deg[maxn];
int num=0;
void bfs (int u){
    num++;
    queue < int > que;
    que.push (u);
    while (!que.empty()){
        int op=que.front(); que.pop();
        bel[op]=num;
        for (int i=head[op];i;i=nex[i]){
            int v=to[i];
            if (!bel[v]) que.push (v);
        } 
    }
}
long long dis[maxn];
long long d[maxn];
void top (){
    queue < int > que;
    for (register int i=1;i<=n;++i) if (deg[i]==1) que.push (i);
    while (!que.empty()){
        int op=que.front(); que.pop();
        for (int i=head[op];i;i=nex[i]){
            int v=to[i];
            if (deg[v]>=2){
                d[bel[op]]=max (d[bel[op]],dis[op]+dis[v]+val[i]);
                dis[v]=max (dis[v],dis[op]+val[i]);
                deg[v]--;
                if (deg[v]==1) que.push (v);
            }
        }
    } 
}
long long a[maxn<<1],b[maxn<<1];
long long ans=0;
bool vis[maxn];
int q[maxn<<2];
void solve (int x,int y){
    int siz=0,c=y;
    int whiler;
    do{
        a[++siz]=dis[c];
        deg[c]=1;
        for (whiler=head[c];whiler;whiler=nex[whiler]){
            int v=to[whiler];
            if (deg[v]>=2){
                c=v;
                b[siz+1]=b[siz]+val[whiler];
                break ;
            }
        }
    }while (whiler);
    int s=0;
    if (siz==2){
        for (int i=head[c];i;i=nex[i])
        {
            int v=to[i];
            if (v==y) s=max (s,val[i]);
        }
        d[x]=max (d[x],dis[y]+dis[c]+s);
        return ;
    }
    for (int i=head[c];i;i=nex[i]){
        int v=to[i];
        if (v==y)
        {
            b[siz+1]=b[siz]+val[i];
            break;
        }
    }
    for (int i=1;i<siz;++i){
        a[siz+i]=a[i]; b[siz+i]=b[siz+1]+b[i];
    }
    int l=1,r=1;
    q[1]=1;
    for (int i=2;i<2*siz;++i){
        if (l<=r&&i-q[l]>=siz) l++;
        d[x]=max (d[x],a[i]+a[q[l]]+b[i]-b[q[l]]);
        while (l<=r&&a[q[r]]+b[i]-b[q[r]]<=a[i]) r--;
        q[++r]=i;
    }
    return ;
}
int main(){
    read (n);
    for (register int i=1;i<=n;++i){
        int x,y; read (x); read (y);
        add (i,x,y); add (x,i,y);
        deg[i]++; deg[x]++;
    }
    for (register int i=1;i<=n;++i) if (!bel[i]) bfs (i);
    top ();
    for (register int i=1;i<=n;++i) if (!vis[bel[i]]&&deg[i]>=2){
        vis[bel[i]]=1;
        solve (bel[i],i);
        ans+=d[bel[i]];
    }
    printf ("%lld",ans);
    return 0;
}