记录编号	585956	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[IOI 2008] 岛屿	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.653 s
提交时间	2023-12-31 22:33:22	内存使用	42.04 MiB

#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 2e6+100;
//基环树好题 
int n;
struct made{
	int ver,nx,ed;
}e[N<<1];
int hd[N],v[N],tot,cnt;
ll q[N],ri[N],ans;
ll a[N],d[N],w[N],dep[N];
bool vi[N];
void add(int x,int y,int z){
	tot++;
	e[tot].ver = y,e[tot].nx = hd[x],e[tot].ed = z,hd[x] = tot;
}
bool find_ring(int x,int in_){
	if(v[x]){v[x] = 2,vi[x] = 1,ri[++cnt] = x;return 1;}
	v[x] = 1;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver;
		if(i == (in_^1))continue;
		if(find_ring(y,i)){
			w[cnt] = e[i].ed;
			if(v[x] == 2)return 0;
			vi[x] = 1,ri[++cnt] = x;
			return 1;
		}
	}
	return 0;
}//找环 
ll s;
void dp(int x,int u){
	vi[x] = 1;
	for(int i = hd[x];i;i = e[i].nx){
		int y = e[i].ver,z = e[i].ed;
		if(vi[y])continue;
		dep[y] = dep[x] + z;
		a[u] = max(a[u],dep[y]);
		dp(y,u);
		s = max(s,d[x]+d[y]+z);
		d[x] = max(d[x],d[y]+z);
	}
}//书上求直径 
int main(){
	freopen("isl.in","r",stdin);
	freopen("isl.out","w",stdout);
    scanf("%d",&n);
    tot = 1;
    for(int i = 1;i <= n;i++){
    	int y,z;
    	scanf("%d%d",&y,&z);
    	add(i,y,z),add(y,i,z);
	}
	for(int i = 1;i <= n;i++)
		if(!vi[i]){
			cnt = 0,s = 0;
			find_ring(i,0);
			for(int i = 1;i <= cnt;i++){
				a[i] = 0;
				dp(ri[i],i);
			}
			//dp 
			for(int i = 1;i <= cnt;i++){
				a[cnt+i] = a[i];
				w[cnt+i] = w[i];
			}
			for(int i = 1;i <= 2*cnt;i++)w[i] += w[i-1];
			//
			int l = 1,r = 1;q[1] = 1;
			for(int i = 2;i <= 2*cnt;i++){
				while(l <= r && i - q[l] >= cnt)l++;
				s = max(s,a[i]+a[q[l]]+w[i-1]-w[q[l]-1]);
				while(l <= r && a[q[r]]-w[q[r]-1] < a[i]-w[i-1])r--;
				q[++r] = i;
			}///
			ans += s;
		}
	printf("%lld\n",ans);
	
	return 0;
}