题意：给定一个基环树森林，求每个基环树的直径之和。
我们发现，一棵基环树的直径只有下面两种情况：
- 环上的某一点作为根的子树的直径。
- 环上有两点，每个点引出一条链，然后再将这两点相连。
对于第一种情况，我们仅需用树形dp的方法求出每个子树的直径（见OI Wiki - 方法2，以后会写直径的笔记），然后比较出最大值即可。这里使用拓扑排序解决。
而第二种情况，我们首先需要记录环上每个节点\(i\)为根的子树中，从\(i\)出发的最长路径。我们将其记为\(f[i]\)（这个\(f\)正好可以用于计算情况\(1\)的子树直径）。
那么接下来我们只需要解决：在环上找到\(i,j\)两点（\(i<j,j-i<n\)），使得\(f[i]+f[j]+dist(i,j)\)最大（\(dist(i,j)\)表示\(i\)到\(j\)的最大距离）。
由于我们断环为链，所以对这条链的节点求一个距离的前缀和，即用\(dis[i]\)表示从链的左端到链的节点\(i\)的距离。如此，我们需要使\(f[i]+f[j]+dis[j]-dis[i]\)最大。
整理得\(f[j]+dis[j]+(f[i]-dis[i])\)。我们发现可以用单调队列优化。枚举右边界\(j\)，然后对于每一个\(j\)，找满足\(j-n+1\le i<j\)的最大\(f[i]-dis[i]\)即可，此时的答案是\(f[j]+dis[j]+f[i]-dis[i]\)。
实现细节：
- 开
long long。 - 可能需要用较快的读入方式。
- 由于是无向图，所以拓扑排序需要稍加修改，见代码。
- 处理环的过程中可能会遇到大小为\(2\)的环。此时拆成链的操作不是很好写，可以特判以下。
- 单调队列优化时，因为\(j\ne i\)，所以遍历前应当先加入决策\(1\)，再从\(2\)开始遍历。遍历过程中，需要先更新最大值，再把当前元素入队列，具体见代码。
点击查看代码
//P4381
#include<bits/stdc++.h>
#define int long long
using namespace std;
struct edge{int to,w;};
int n,deg[1000010],f[1000010],ans,cnt;
//deg[i]：i的度，用于拓扑排序
//f[i]：以i为根的子树中，从i出发的最长路径
int ff[1000010];
//ff[i]：断成链后每个点对应的的f
bool vis[1000010];
int d[500010],num[1000010],fir;
//d[i]：编号为i的连通块的答案
//num[i]：节点i所属连通块编号
int dis[1000010];
vector<edge> G[1000010];
queue<int> q;
deque<int> de;
void add(int u,int v,int w){
G[u].push_back({v,w});
deg[v]++;
}
void dfs(int pos){//为每个连通块编号
if(vis[pos]) return;
vis[pos]=1,num[pos]=cnt;
for(auto i:G[pos]) dfs(i.to);
}
void topo(){//寻找环，并且计算子树直径
for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i);
while(!q.empty()){
int u=q.front();
q.pop();
for(auto i:G[u]){
int v=i.to,w=i.w;
if(deg[v]>1){//u是v的子节点
d[num[v]]=max(d[num[v]],f[v]+f[u]+w);
f[v]=max(f[v],f[u]+w);
deg[v]--;
if(deg[v]==1) q.push(v);
}
}
}
}
void cycle(int pos,int cnt){//处理环
vis[pos]=1;
ff[cnt]=f[pos];
bool end=1;
int tempw=-1;
for(auto i:G[pos]){
int v=i.to,w=i.w;
if(v==fir) tempw=w;
if(vis[v]||deg[v]==1) continue;
dis[cnt+1]=dis[cnt]+w,end=0;
cycle(v,cnt+1);
break;
}
if(end){
int tnum=num[fir];
if(cnt==2){//特判2个节点的环
for(auto i:G[pos]){
int v=i.to,w=i.w;
if(v==fir) d[tnum]=max(d[tnum],w+f[pos]+f[v]);
}
return;
}
for(int i=cnt+1;i<=2*cnt-1;i++){
if(i==cnt+1) dis[i]=dis[i-1]+tempw;
else dis[i]=dis[i-1]+dis[i-cnt]-dis[i-cnt-1];
ff[i]=ff[i-cnt];
}
de.clear();
de.push_back(1);
for(int i=2;i<=2*cnt-1;i++){
if(!de.empty()&&i-de.front()>=cnt) de.pop_front();
d[tnum]=max(d[tnum],ff[i]+dis[i]+ff[de.front()]-dis[de.front()]);
while(!de.empty()&&ff[i]-dis[i]>=ff[de.back()]-dis[de.back()])
de.pop_back();
de.push_back(i);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
for(int i=1;i<=n;i++){
int u,w;
cin>>u>>w;
add(i,u,w),add(u,i,w);
}
for(int i=1;i<=n;i++)//为每个连通块编号
if(!vis[i]) ++cnt,dfs(i);
topo();//计算情况1
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)//计算情况2
if(!vis[i]&°[i]!=1) fir=i,cycle(i,1);
for(int i=1;i<=cnt;i++) ans+=d[i];
cout<<ans;
return 0;
}