Solution
因为有 (n) 个点和 (n) 条边，所以这就是一个基环树森林。
那么题目让我们求的就是基环树的直径之和。
基环树的直径只有两种可能：1.在以环上某一点为根的子树中 2.在两颗子树中并经过环上一部分
那么分别求出两种可能的最大值然后比较大小即可。
对于第一种可能，选择对每一棵树进行树形DP，正常求树的直径。
同时要记录下来 (len) 数组，其中 (len_i) 表示以环上第 (i) 个点为根的子树中，到根最大的距离。这是为了第二种可能准备。
对于第二种可能，设环为 (E) ，我们只要求出 (maxlimits_{i,jin E,j<i}{len_i+len_j+dis_{i,j}}) 。
但是如果枚举 (i,j) 的话复杂度是不允许的。我们将环破为链，并且复制成两倍，设 (sum_{i}) 表示从 (1) 到 (i) 的 (dis) 的前缀和，也就是 (sum_i=sum_{i-1}+dis_{i-1,i}) ，那么上面的式子就成了 (len_i+len_j+sum_i-sum_j ightarrow len_i+sum_i+len_j-sum_j) 。
将 (i) 固定，只考虑 (j) ，那么对于两个点 (j,k) ， 如果有 (len_j-sum_j<len_k-sum_k) ，那么肯定选择 (k) ，所以用单调队列优化DP。
Code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
ll n,tot,cnt,ans,st,ans1,ans2,ans3;
ll head[N];
struct edge{
int to,nxt,w;
}e[N<<1];
ll vis1[N],vis2[N],dfn[N],d[N],dp[N<<1],s[N];
inline void add(int u,int v,int w){
e[++tot].to=v;
e[tot].w=w;
e[tot].nxt=head[u];
head[u]=tot;
}
bool dfs(int x,int pre){
if(vis1[x]==1){
vis1[x]=2,dfn[++cnt]=x,vis2[x]=1;
return 1;
}
vis1[x]=1;
for(int i=head[x];i;i=e[i].nxt)
if(i!=((pre-1)^1)+1&&dfs(e[i].to,i)){
if(vis1[x]!=2) dfn[++cnt]=x,vis2[x]=1,s[cnt]=s[cnt-1]+e[i].w;
else{
s[st-1]=s[st]-e[i].w;
return 0;
}
return 1;
}
return 0;
}
inline void tree_dp(int now){
vis2[now]=1;
for(int i=head[now];i;i=e[i].nxt){
int y=e[i].to;
if(vis2[y]) continue;
tree_dp(y);
ans=max(ans,d[now]+d[y]+e[i].w);
d[now]=max(d[now],d[y]+e[i].w);
}
}
inline ll query(int rt){
st=cnt+1,ans2=0,ans3=0;
dfs(rt,0);
for(int i=st;i<=cnt;i++){
ans=0;
tree_dp(dfn[i]);
ans2=max(ans2,ans);
dp[i+cnt-st+1]=dp[i]=d[dfn[i]];
s[i+cnt-st+1]=s[i+cnt-st]+s[i]-s[i-1];
}
deque<int> q;
for(int i=st;i<=2*cnt-st+1;i++){
while(q.size()&&q.front()<=i-cnt+st-1) q.pop_front();
if(q.size()) ans3=max(ans3,dp[i]+dp[q.front()]+s[i]-s[q.front()]);
while(q.size()&&dp[q.back()]-s[q.back()]<=dp[i]-s[i]) q.pop_back();
q.push_back(i);
}
return max(ans2,ans3);
}
int main(){
scanf("%lld",&n);
for(int i=1,y,z;i<=n;i++){
scanf("%d%d",&y,&z);
add(i,y,z);add(y,i,z);
}
for(int i=1;i<=n;i++)
if(!vis2[i]) ans1+=query(i);
printf("%lld
",ans1);
return 0;
}