代码还是放出来算了，但是不指望能看得懂（）
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
typedef long long LL;
typedef pair<int,int> pii;
int n;
vector<pii>g[MAXN];
vector<int>eid[MAXN];int ecnt=1;
vector<int>cir[MAXN];
LL cirnxtdis[MAXN];
int dfn[MAXN],dfncnt=0,low[MAXN],sccnum[MAXN],scccnt=0,sccfirst[MAXN];
bitset<MAXN>iscir;
void tarjan(int x){//Get SCC
static stack<int>st;
static bool instack[MAXN];
dfn[x]=low[x]=++dfncnt;
st.push(x);instack[x]=1;
int v;
for(auto it:g[x]){
v=it.first;
if(!dfn[v]){
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(instack[v]){
low[x]=min(low[x],dfn[v]);
}
}
if(dfn[x]==low[x]){
scccnt++;
while(st.top()!=x){
sccnum[st.top()]=scccnt;
instack[st.top()]=0;
st.pop();
}
sccnum[x]=scccnt;
sccfirst[scccnt]=x;
instack[x]=0;
st.pop();
}
}
stack<int>fc_st,fc_st_dis;
bitset<MAXN>fc_vis;
bool fc_isbreak;
void FindCircle(int x,int fa,int id,int inid){
fc_vis[x]=1;
for(int i=0;i<g[x].size();i++){
auto it=g[x][i];
if(fc_isbreak) return;
if(eid[x][i]==(inid^1) || sccnum[it.first]!=id) continue;
if(fc_vis[it.first]){
while((!fc_st.empty()) && fc_st.top()!=it.first){
iscir[fc_st.top()]=1;
cir[id].push_back(fc_st.top());
cirnxtdis[fc_st.top()]=fc_st_dis.top();
fc_st.pop();
fc_st_dis.pop();
}
iscir[it.first]=1;
cir[id].push_back(it.first);
cirnxtdis[it.first]=it.second;
fc_isbreak=1;
return;
}
else{
fc_st.push(it.first);
fc_st_dis.push(it.second);
FindCircle(it.first,x,id,eid[x][i]);
if(fc_isbreak) return;
fc_st_dis.pop();
fc_st.pop();
}
}
}
// LL diam[MAXN];
LL diamres;
void GetSubtreeDiam(int u,int fa){
static LL f[MAXN];
int v;
for(auto it:g[u]){
v=it.first;
if(v==fa || iscir[v]) continue;
GetSubtreeDiam(v,u);
diamres=max(diamres,f[u]+f[v]+it.second);
f[u]=max(f[u],f[v]+it.second);
}
}
LL dep[MAXN],depres;
void GetSubtreeDepth(int x,int fa,LL d){
depres=max(depres,d);
int v;
for(auto it:g[x]){
v=it.first;
if(v==fa || iscir[v]) continue;
GetSubtreeDepth(v,x,d+it.second);
}
}
LL ans,anssum=0;
int dblcir[MAXN<<1];
LL cirdis[MAXN<<1];
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int u=1,v,w;u<=n;u++){
cin>>v>>w;
ecnt++;
g[u].emplace_back(v,w);eid[u].push_back(ecnt);
ecnt++;
g[v].emplace_back(u,w);eid[v].push_back(ecnt);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
for(int i=1;i<=scccnt;i++){
fc_isbreak=0;
while(!fc_st.empty()) fc_st.pop();
while(!fc_st_dis.empty()) fc_st_dis.pop();
fc_st.push(sccfirst[i]);
fc_st_dis.push(0);
FindCircle(sccfirst[i],-1,i,0);
// cout<<i<<':'<<endl;
// for(auto it:cir[i]){
// cout<<it<<' '<<cirnxtdis[it]<<endl;
// }
}
// cout<<endl;
for(int i=1;i<=scccnt;i++){
ans=0;
int ptr=1;
for(auto it:cir[i]){
diamres=0;
GetSubtreeDiam(it,-1);
ans=max(ans,diamres);
// cout<<it<<' '<<diamres<<endl;
depres=0;
GetSubtreeDepth(it,-1,0);
// cout<<it<<' '<<depres<<endl;
dep[it]=depres;
dblcir[ptr]=dblcir[ptr+cir[i].size()]=it;
ptr++;
}
cirdis[0]=0;
for(int j=2;j<=2*cir[i].size()+1;j++){
cirdis[j]=cirdis[j-1]+cirnxtdis[dblcir[j-1]];
}
// for(int j=1;j<=2*cir[i].size()+1;j++){
// cout<<j<<' '<<dblcir[j]<<' '<<cirnxtdis[dblcir[j]]<<' '<<cirdis[j]<<endl;
// }
deque<int>q;
for(int j=1;j<=2*cir[i].size();j++){
while((!q.empty())&&(q.front()<=(j-(int)cir[i].size()))) q.pop_front();//STL容器的size类型是ULL，所以如果会出现负数要强制转换类型！
// cout<<q.size()<<endl;
if(!q.empty()){
ans=max(ans,dep[dblcir[q.front()]]+dep[dblcir[j]]+cirdis[j]-cirdis[q.front()]);
// cout<<j<<' '<<dblcir[j]<<' '<<dep[dblcir[q.front()]]<<' '<<dep[dblcir[j]]<<' '<<cirdis[j]<<' '<<cirdis[q.front()]<<endl;
}
while((!q.empty())&&(dep[dblcir[q.back()]]-cirdis[q.back()]<=dep[dblcir[j]]-cirdis[j])) q.pop_back();
q.push_back(j);
}
// cout<<"-------"<<endl;
// cout<<ans<<endl;
anssum+=ans;
}
cout<<anssum;
return 0;
}
```
by MessageBoxA @ 2023-11-08 18:33:45
建议使用快读快写
by MyNameIsikun @ 2024-01-06 15:06:48