无法解释啊

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N=1e6+5;

struct oi {
	int to;
	int w;
	int id;
};

struct oi2 {
	int pos;
	ll val;
};

ll edge[2*N],head[N],ver[2*N],nt[2*N];
ll tot;

 void add(int x,int y,int z) {
    edge[++tot]=z,ver[tot]=y,nt[tot]=head[x],head[x]=tot;
}



int n;
ll d[N*2];
int vis[N];
int vis2[N];
int nxt[N];
int nxt_w[N];
int fnxt[N];
int fnxt_w[N];
int c[N];
ll f[N][2];
ll g[N];
ll s[N*2];
ll ans;

void read() {
	cin>>n;
	for(int i=1; i<=n; i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		add(u,i,v);
		add(i,u,v);
	}
}

int flag;
int h;

void dfs(int u,int id) {
	vis[u]=1;
	for(int i=head[u]; i; i=nt[i]) {
		int v= ver[i];
		int w=  edge[i];
		if(i==((id-1)^1)+1||c[v]) continue ;
		if(vis[v]) {
			h=v;
			nxt[u]=v;
			nxt_w[u]=w;
			fnxt[v]=u;
			fnxt_w[v]=w;
			c[u]=1;
			flag=1;
			return ;
		}
		dfs(v,i);
		if(flag==1) {
			fnxt[v]=u;
			fnxt_w[v]=w;
			nxt[u]=v;
			nxt_w[u]=w;
			c[u]=1;
			if(u==h) flag=2;
			return ;
		}
		if(flag==2) return ;
	}
}

void dfs2(int u,int fa) {
	for(int i=head[u]; i; i=nt[i]) {
		int v=ver[i];
		int w=edge[i];
		if(v==fa||c[v]) continue ;
		dfs2(v,u);

		if(f[v][0]+w>=f[u][0]) {
			f[u][1]=f[u][0];
			f[u][0]=f[v][0]+w;
		} else if(f[v][0]+w>=f[u][1]) f[u][1]=f[v][0]+w;
		else if(f[v][1]>0&&f[v][1]+w>=f[u][0]) {
			f[u][1]=f[u][0];
			f[u][0]=f[v][1]+w;
		} else if(f[v][1]>0&&f[v][1]+w>=f[u][1]) f[u][1]=w+f[v][1];

		g[u]=max(g[u],g[v]);
	}
	g[u]=max(g[u],f[u][0]+f[u][1]);
}

void init() {
	for(int i=1; i<=n; i++)
		if(!vis[i])
			flag=h=0,dfs(i,0);
			
	for(int i=1; i<=n; i++)
		if(c[i])
			dfs2(i,0);
}
	
deque<oi2>q;

void work() {
	
	for(int i=1; i<=n; i++)
		if(c[i]&&vis2[i]==0) {
			ll res=0;

			while(!q.empty()) q.pop_back();
			int len=0;
			int st=i;
			while(vis2[st]==0) {
				res=max(res,1ll*g[st]);
				vis2[st]=1;
				d[++len]=f[st][0];
				s[len]=nxt_w[st];
				st=nxt[st];
			}

			for(int j=1; j<=len; j++) d[j+len]=d[j],s[j+len]=s[j];
			ll w=0;
			for(int j=2; j<=len; j++) {
				w+=1ll*s[j-1];
				while(!q.empty()&&w+1ll*d[j]>=q.back().val) q.pop_back();
				oi2 tmp;
				tmp.pos=j;
				tmp.val=w+1ll*d[j];
				q.push_back(tmp);
			}

			res=max(res,1ll*d[1]+q.front().val);
			
			ll w2=0;
			for(int j=2; j<=len; j++) {
				while(!q.empty()&&q.front().pos<=j) q.pop_front();
				w2+=1ll*s[j-1];
				w+=1ll*s[j+len-2];
				while(!q.empty()&&w+1ll*d[j+len-1]>=q.back().val) q.pop_back();
				oi2 tmp;
				tmp.pos=j+len-1;
				tmp.val=w+1ll*d[j+len-1];
				q.push_back(tmp);
				res=max(res,1ll*d[j]+q.front().val-w2);
			}
			
			while(!q.empty()) q.pop_back();
			len=0;
			st=i;
			while(1) {
				res=max(res,1ll*g[st]);
				vis2[st]=1;
				d[++len]=f[st][0];
				s[len]=fnxt_w[st];
				st=fnxt[st];
				if(st==i) break;
			}

			for(int j=1; j<=len; j++) d[j+len]=d[j],s[j+len]=s[j];
			w=0;
			w2=0;
			
			for(int j=2; j<=len; j++) {
				w+=1ll*s[j-1];
				while(!q.empty()&&w+1ll*d[j]>=q.back().val) q.pop_back();
				oi2 tmp;
				tmp.pos=j;
				tmp.val=w+1ll*d[j];
				q.push_back(tmp);
			}

			res=max(res,1ll*d[1]+q.front().val);
		
			for(int j=2; j<=len; j++) {
				while(!q.empty()&&q.front().pos<=j) q.pop_front();
				w2+=1ll*s[j-1];
				w+=1ll*s[j+len-2];
				while(!q.empty()&&w+1ll*d[j+len-1]>=q.back().val) q.pop_back();
				oi2 tmp;
				tmp.pos=j+len-1;
				tmp.val=w+1ll*d[j+len-1];
				q.push_back(tmp);
				res=max(res,1ll*d[j]+q.front().val-w2);
			}

			ans+=res;
		}
	cout<<ans<<endl;
}

signed main() {
	freopen("a.txt","r",stdin);
	read();
	init();
	work();
	return 0;
}