如题，复制三次的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e18+114;
const int maxn = 1e6+114;
int uu[maxn],vv[maxn];
int U,V;
int fa[maxn];
int wfa[maxn];
int n;
int found(int u){
	return fa[u]=(fa[u]==u?u:found(fa[u]));
}
vector< pair<int,int> > E[maxn];  
int use[maxn];
int dep[maxn];
int vis[maxn];
int father[maxn];
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	father[u]=fa;
	use[u]=1;
	for(pair<int,int> e:E[u]){
		int v=e.first,w=e.second;
		if(use[v]==1) continue;
		wfa[v]=w;
		dfs(v,u);
	}
}
int dp[maxn];
int ans;
int d;
void DP(int u,int fa){
	dp[u]=0;
	for(pair<int,int> e:E[u]){
		int v=e.first,w=e.second;
		if(vis[v]==0&&v!=fa){
			DP(v,u);
			dp[v]+=w;
			d=max(d,dp[u]+dp[v]);
			dp[u]=max(dp[u],dp[v]);
		}
	}
}
int weight[maxn];
vector<int> H;//环上点 
vector< pair<pair<int,int>,int> > vec;
pair<int,int> q[maxn<<1];
int l,r;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++){
		int w;
		int u=i,v;
		cin>>v;
		cin>>w;
		if(found(u)!=found(v)){
			E[u].push_back(make_pair(v,w));
			E[v].push_back(make_pair(u,w));
			fa[found(v)]=found(u);
		}else vec.push_back(make_pair(make_pair(u,v),w));
	}
	for(pair<pair<int,int>,int> e:vec) uu[found(e.first.first)]=e.first.first,vv[found(e.first.second)]=e.first.second,weight[found(e.first.first)]=e.second;
	int ans=0;
	for(int i=1;i<=n;i++){
		if(use[i]==0){
			U=uu[found(i)],V=vv[found(i)];
			dfs(V,0);
			if(dep[U]<dep[V]) swap(U,V);
			d=0;
			H.clear();
			while(U!=father[V]){
				H.push_back(U);
				U=father[U];
			}
			wfa[V]=weight[found(i)];
			for(int x:H) vis[x]=1;
			for(int x:H) DP(x,0);
			//cout<<"-------------\n";
			l=1,r=0;
			int tag=0;//单调队列整体加
			for(int j=0;j<3*H.size();j++){
				while(r>=l&&q[l].first<=j-H.size()){
					l++;
				}
				if(r>=l){
					//cout<<"ask"<<H[j%H.size()]<<' '<<q[l].second+tag<<' '<<dp[H[j%H.size()]][0]<<'\n';
					d=max(d,dp[H[j%H.size()]]+q[l].second+tag);
				}
				while(r>=l&&q[r].second+tag<dp[H[j%H.size()]]){
					r--;
				}
				//cout<<"ins"<<dp[H[j%H.size()]][0]-tag<<"\n";
				q[++r]=make_pair(j,dp[H[j%H.size()]]-tag);
				tag+=wfa[H[j%H.size()]];
			}
			ans+=d;
		}
	}
	cout<<ans<<'\n';
	return 0;
}