好久没做题了，来水个水题题解（虽然是个 IOI）。
首先只考虑把桥当做边。那么同一个连通块里的显然不能坐船。然后你在某个连通块走了若干桥后，突然坐船到了另一个连通块，相当于把这个两个连通块连通了。如此下去，最终答案就是每个连通块的最长链加起来。
现在要求给定连通块的最长链。在一般图上看起来不太可做。但这题构图特殊，每个点连出去一条边，那么对一个 (n) 个点的连通块就有 (n) 条边。而它又是连通的，根据相关定理知道一定是基环树。
那就分成两部分：
- 在环上某个点的子树内，那就求直径瞎搞搞就可以了；
- 绕了一段环。那就是两端往子树下面尽可能伸长。考虑 (f_i) 表示点 (i) 下的子树往下跑的最长链。在某个地方断环成链，顺时针逆时针分别试一波，这里以顺时针举例。考虑 (D_i) 表示断环成链并复制一遍后，(a_i o a_{i+1}) 的边长的前缀和。那么 (a_l,a_r) 的 value 就是 (f_{a_l}+f_{a_r}+D_{a_r-1}-D_{a_l-1})。枚举 (r)，然后记录最大的 (f_{a_l}-D_{a_l-1})。由于断环成链了，太往前不可取，可以单调队列或者劣一点但是好写一点的优先队列。复杂度 (mathrm O(n)) 或 (mathrm O(nlog n))。
第一次写基环树，code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define X first
#define Y second
#define mp make_pair
const int N=1000000;
int n;
vector<pair<int,int> > nei[N+1];
bool vis[N+1];
vector<int> cc;
void dfs(int x){
vis[x]=true;
cc.pb(x);
for(int i=0;i<nei[x].size();i++){
int y=nei[x][i].X;
if(!vis[y])dfs(y);
}
}
bool vis0[N+1];
int fa[N+1];
int st,ed;
void dfs0(int x){
vis0[x]=true;
bool faed=false;
for(int i=0;i<nei[x].size();i++){
int y=nei[x][i].X;
if(!faed&&y==fa[x]){faed=true;continue;}
if(vis0[y]){st=y;ed=x;continue;}
fa[y]=x;
dfs0(y);
}
}
int ban[N+1][2];
int ans;
int dp[N+1];
void dfs1(int x,int fa0=0){
int mx1=0,mx2=0;
for(int i=0;i<nei[x].size();i++){
int y=nei[x][i].X,len=nei[x][i].Y;
if(y==fa0||y==ban[x][0]||y==ban[x][1])continue;
dfs1(y,x);
dp[x]=max(dp[x],dp[y]+len);
if(dp[y]+len>mx1)mx2=mx1,mx1=dp[y]+len;
else if(dp[y]+len>mx2)mx2=dp[y]+len;
}
ans=max(ans,mx1+mx2);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,len;
scanf("%lld%lld",&x,&len);
nei[i].pb(mp(x,len)),nei[x].pb(mp(i,len));
}
int Ans=0;
for(int i=1;i<=n;i++)if(!vis[i]){//remember to make it first
ans=0;
cc.clear();
dfs(i);
dfs0(cc[0]);
vector<int> root,to,To;
while(true){
root.pb(st);
if(st==ed)break;
st=fa[st];
}//之所以要你到山顶上去，不是要全世界看到你，而是要你看到全世界。——yyq
for(int j=0;j<root.size();j++){
ban[root[j]][0]=j==0?root.back():root[j-1];
ban[root[j]][1]=j==root.size()-1?root[0]:root[j+1];
}
for(int j=0;j<root.size();j++)dfs1(root[j]);
/*------------------------------------copy start-----------------------------------*/
if(root.size()==2){
st=root[0];
for(int j=0;j<nei[st].size();j++)if(nei[st][j].X==ed)to.pb(nei[st][j].Y);
}
else{
for(int j=0;j<root.size();j++){
int x=root[j],y=root[(j+1)%root.size()];
for(int k=0;k<nei[x].size();k++)if(nei[x][k].X==y)to.pb(nei[x][k].Y);
}
}
for(int j=0;j<2*to.size();j++)To.pb((j==0?0:To[j-1])+to[j%to.size()]);
priority_queue<pair<int,int> > q;
for(int j=1;j<to.size();j++)q.push(mp(-To[j-1]+dp[root[j]],j));
for(int j=to.size();j<2*to.size();j++){
while(q.top().Y<=j-to.size())q.pop();
ans=max(ans,q.top().X+dp[root[j%to.size()]]+To[j-1]);
q.push(mp(-To[j-1]+dp[root[j%to.size()]],j));
}
/*-------------------------------------copy end------------------------------------*/
reverse(root.begin(),root.end());
to.clear(),To.clear();
/*------------------------------------paste start-----------------------------------*/
if(root.size()==2){
for(int j=0;j<nei[st].size();j++)if(nei[st][j].X==ed)to.pb(nei[st][j].Y);
}
else{
for(int j=0;j<root.size();j++){
int x=root[j],y=root[(j+1)%root.size()];
for(int k=0;k<nei[x].size();k++)if(nei[x][k].X==y)to.pb(nei[x][k].Y);
}
}
for(int j=0;j<2*to.size();j++)To.pb((j==0?0:To[j-1])+to[j%to.size()]);
while(q.size())q.pop();
for(int j=1;j<to.size();j++)q.push(mp(-To[j-1]+dp[root[j]],j));
for(int j=to.size();j<2*to.size();j++){
while(q.top().Y<=j-to.size())q.pop();
ans=max(ans,q.top().X+dp[root[j%to.size()]]+To[j-1]);
q.push(mp(-To[j-1]+dp[root[j%to.size()]],j));
}
/*-------------------------------------paste end------------------------------------*/
Ans+=ans;
}
cout<<Ans;
return 0;
}