记录编号	23536	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[IOI 2008] 岛屿	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	2.329 s
提交时间	2011-03-14 21:09:25	内存使用	103.26 MiB

#include <stdio.h>
#include <string.h>
#define N 1000010
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define FOR(i,l,r) for (int i=l;i<=r;++i)

int u[N*2],v[N*2],next[N*2],fir[N],pg=1;
int p[N],q[N*2],l[N*2],len,head,tail,n;
int vis[N],flag;
long long f[N],w[N*2],b[N*2],c[N*2],ans_b,ans;

void add(int _u,int _v,int _w) {
    ++pg; u[pg]=_u; v[pg]=_v; w[pg]=_w; next[pg]=fir[_u]; fir[_u]=pg;
    ++pg; u[pg]=_v; v[pg]=_u; w[pg]=_w; next[pg]=fir[_v]; fir[_v]=pg;
}

int bfs(int from) {
    head=0; tail=0; int cir=0;
    q[tail]=from; vis[from]=flag;
    while (head<=tail) {
        int now=q[head++];
        for (int j=fir[now];j;j=next[j]) 
            if (vis[v[j]]!=flag)
                vis[v[j]]=flag ,p[v[j]]=j ,q[++tail]=v[j];
            else if (p[now]!=(j^1)) cir=j;
    }
    return cir;
}

void dp(int from) {
    bfs(from);
    while (tail>=0) {
        int i=q[tail]; long long&res=f[i];
        for (int j=fir[i];j;j=next[j]) if (p[v[j]]==j) {
            long long now=f[i]+f[v[j]]+w[j];
            if (now>ans_b) ans_b=now;
            if (f[v[j]]+w[j]>res) res=f[v[j]]+w[j];
        }
        --tail;
    }
}

void get_cir(int from) {
    ++flag;
    int i,c=bfs(from);
    
    ++flag; for (i=u[c];i;i=u[p[i]]) vis[i]=flag;
    ++flag; len=N;
    for (i=v[c];vis[i]!=flag-1;i=u[p[i]])
        vis[i]=flag, --len, l[len]=i, b[len]=w[p[i]];
    --len; l[len]=i; vis[i]=flag;
    
    memmove(l,&l[len],(N-len)*sizeof(int));
    memmove(b,&b[len],(N-len)*sizeof(long long));
    len=N-len; int t=len;
    
    for (i=u[c];vis[i]!=flag;i=u[p[i]])
        l[len]=i, b[++len]=w[p[i]];
    b[0]=b[len]; b[t]=w[c];
}

int main() {
    freopen("isl.in","r",stdin);
    freopen("isl.out","w",stdout);
    scanf("%d",&n);
    
    FOR(u,1,n) {int v,w; scanf("%d%d",&v,&w); add(u,v,w);}
    
    FOR(from,1,n) if (!vis[from]) {
        get_cir(from);
        ++flag; FOR(i,0,len-1) vis[l[i]]=flag,p[l[i]]=0;
        
        ans_b=0;
        FOR(i,0,len-1) {dp(l[i]);c[i]=f[l[i]];}
        
        memcpy(&b[len],b,len*sizeof(long long));
        memcpy(&c[len],c,len*sizeof(long long));
        FOR(i,1,len*2-1) b[i]+=b[i-1];
        long long temp;
        FOR(i,0,len*2-1) {
            temp=c[i]-b[i];
            c[i]+=b[i]; b[i]=temp;
        }
        
        head=0; tail=-1;
        FOR(i,0,len*2-1) {
            if (i>=len) {
                while (head<=tail && q[head]<=i-len) ++head;
                temp=b[q[head]]+c[i];
                if (temp>ans_b) ans_b=temp;
            }
            while (head<=tail && b[i]>b[q[tail]]) --tail;
            q[++tail]=i;
        }
        ans+=ans_b;
    }
    printf("%lld\n",ans);
}