RT，使用tarjan求环，DP求子树直径，贪心求总最大直径。

通过对拍发现在一些大数据范围下，Tarjan求环会出现只取到了一些环的现象，而小范围数据目前暂时没有发现问题，估计某处写挂，或者某处做法写假了。

求大佬帮忙调试，蒟蒻会关注回报的！

代码如下：

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int N=2e6+10;
int n,a[N];
#define ll long long
#define int long long
int he[N],ne[N],to[N],tot=1;
long long w[N],d[N],dist[N],ans,sum,ringlen;
ll read(){
	ll x=0;char ch=getchar();
	while(ch<'0'||'9'<ch) ch=getchar();
	while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar(); }
	return x;
}
void addedge (int x,int y,long long z){
	to[++tot]=y;
	ne[tot]=he[x];
	he[x]=tot;
	w[tot]=z;
}
int low[N],dfo[N],cnt=0,edcccnt=0;
stack <int> q;
vector <int> edcc[N];
bool st[N],bridge[N],node[N],vis[N];
void tarjan(int now,int inedge){
	dfo[now]=low[now]=++cnt;
	q.push(now);
	st[now]=1;
	for(int i=he[now];i;i=ne[i]){
		int v=to[i];
		if(!dfo[v]){
			tarjan(v,i);
			low[now]=min(low[now],low[v]);
			if(low[v]>dfo[now]){
				bridge[i]=bridge[i^1]=true;
				++edcccnt;
				int p;
				do{
					p=q.top();
					edcc[edcccnt].push_back(p);
					st[p]=0;
					q.pop();
				}
				while(p!=v);
				if(edcc[edcccnt].size()==1){
					edcc[edcccnt].clear();
					--edcccnt;
				}
			}
		}
		else if(i!=(inedge^1)){
			low[now]=min(low[now],dfo[v]);
		}
	}
}
void dp(int now){
	st[now]=true;
	for(int i=he[now];i;i=ne[i]){
		int v=to[i];
		if(st[v]||node[v]){
			continue;
		}
		dp(v);
		sum=max(sum,(long long)d[now]+d[v]+w[i]);
		d[now]=max(d[now],(long long)d[v]+w[i]);
	}
}
int dfs(int now,int fa,long long s,int inedge){
//	cout<<"from "<<fa<<" to "<<now<<" the s: "<<s<<endl;
	dist[++cnt]=s;
	a[cnt]=now;
	if(vis[now]==true){
		return s;
	}
	vis[now]=true;
	for(int i=he[now];i;i=ne[i]){
		int v=to[i];
		if(node[v]==false||i==(inedge^1)){
			continue;
		}
//		cout<<"next is "<<v<<endl; 
		return dfs(v,now,s+w[i],i);
	}
}
signed main(){
	freopen("the.in","r",stdin);
	freopen("the.out2","w",stdout);
	n=read();
	int x,y;
	long long z;
	for(int i=1;i<=n;i++){
		y=read();z=read();
		x=i;
		addedge(x,y,z);
		addedge(y,x,z);
	}
	for(int i=1;i<=n;i++){
		if(!st[i]){
			addedge(i+n,i,0);
			tarjan(i+n,0);
		}
	}
	for(int i=1;i<=edcccnt;i++){
		sum=cnt=0;
		vector<int>::iterator it;
		for(it=edcc[i].begin();it!=edcc[i].end();it++){
			node[*it]=true;
 			cout<<*it<<" ";
		}
 		cout<<endl;
		ringlen=dfs(*edcc[i].begin(),0,0,-1);
		for(int j=1;j<=cnt;j++){
//			cout<<j<<" : "<<a[j]<<" "<<dist[j]<<endl;
		}
		for(int j=cnt+1;j<=(cnt-1)*2;j++){
			a[j]=a[j-(cnt-1)];
			dist[j]=dist[j-1]+(dist[j-(cnt-1)]-dist[j-(cnt-1)-1]);
//			cout<<j<<" : "<<a[j]<<" "<<dist[j]<<endl;
		}
		--cnt;
//		cout<<"ringlen: "<<ringlen<<endl;
		for(int j=1;j<=cnt;j++){
			dp(a[j]);
//			cout<<a[j]<<" : "<<sum<<endl;
		}
		for(int l=2,r=l+cnt-1;l<=cnt+1;l++,r++){
			sum=max(sum,d[a[l]]+d[a[r]]+(dist[r]-dist[l]));
			sum=max(sum,d[a[l]]+d[a[l-1]]+(dist[l]-dist[l-1]));
//			cout<<"from "<<a[l]<<" to "<<a[r]<<" dist: "<<dist[r]-dist[l]<<" sum: "<<sum<<endl;
		}
		ans+=sum;
	}
	printf("%lld\n",ans);
}