Description
一句话题意：给一个基环树森林，求每棵基环树的直径长度的和（基环树的直径定义与树类似，即基环树上一条最长的简单路径），节点总数不超过(10^6)。
Solution
问题就是如何求基环树的直径。
首先树的直径的话可以直接(dp)，那如果有一个环怎么办？
这个环上会挂着几棵树，那么直径只会有两种情况
- 不经过环上的边，即每棵树直径的最大值
- 经过一个环，即挂在换上的两棵树(i,j)的深度和在加上(i,j)在环上的距离
第一种情况直接树形(Dp)求一下树的直径就好了。
第二种情况有点麻烦，为了方便下面令(tree(x))表示以(x)为根挂在环上的树，(depth(T))表示树(T)的深度，(dist(i,j))表示环上两点之间只走环上的边的最大距离（(i,j)在环上只有两条路径）。
那这种情况的答案就是(maxlimits_{i ot= j} {depth(tree(i)) + depth(tree(j)) + dist(i,j)})
下面令(v_1,v_2,...,v_s)表示大小为(s)（点的个数）的环上以逆时针或顺时针的访问顺序依次访问到的(s)个点，(sum_i)表示从(v_1)按顺序走走到(v_i)的环上路径长度。
那么点(i)按一个方向走到点(j)的环上长度就是(sum_j - sum_i)。
我们可以把环复制两倍，然后就能够处理第(2)个方向的距离。
即(v)变为(v_1,v_2,...,v_{s},v_{s+1},...,v_{2s})，那么(v_i)与(v_j)((1 le i<j le 2s, abs(i-j) < n))的最大距离(dist(i,j))就是(max(sum_j - sum_i, sum_{i+s} - sum_j))
这样的话就可以单调队列维护，扫一次(v_{1...2s})就行了。
找环的话可以在(Dfs)树上找，不卡栈空间的（至少(Luogu)是这样......）
Code
#include <bits/stdc++.h>
using namespace std;
template<typename tp> inline void read(tp &x){
x=0; tp f=1; char ch=getchar();
for (;!isdigit(ch);ch=getchar())f=ch=='-'?-f:f;
for (;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
x=x*f;
}
#define pb push_back
#define same(e1,e2) (min(e1^1,e1)==min(e2^1,e2))
typedef long long ll;
const ll INF=1e18;
const int N=2e6+10;
int cnt=1,fst[N],nxt[N<<1],to[N<<1];ll dis[N<<1];
inline void ade(int x,int y,ll w){
to[++cnt]=y,nxt[cnt]=fst[x],fst[x]=cnt;
dis[cnt]=w;
}
inline void addedge(int x,int y,ll w){ade(x,y,w),ade(y,x,w);}
vector<int>ring[N]; int tot=0,dep[N],fa[N];
void dfs(int x,int deep,int lste,int prev){
dep[x]=deep,fa[x]=prev;
for (int i=fst[x];i;i=nxt[i]){
int v=to[i]; //printf("%d->%d
",x,v);
if (dep[v]==0) dfs(v,deep+1,i,x);
else if (!same(i,lste)&&dep[v]<dep[x]){
++tot;for (int nw=x;nw!=v;nw=fa[nw])ring[tot].pb(nw);
ring[tot].pb(v);
}
}
}
int mark[N];ll dp[N],mxdp;
void DP(int x,int prev){
for (int i=fst[x];i;i=nxt[i]){
int v=to[i]; if (mark[v]||v==prev) continue;
DP(v,x);
mxdp=max(dp[x]+dp[v]+dis[i],mxdp);
dp[x]=max(dp[x],dp[v]+dis[i]);
}
}
int vis[N],id[N],tim;ll a[N],b[N];
void getW(int x,ll dd,int lste){
vis[x]++,id[++tim]=x,b[tim]=dd;
for (int i=fst[x];i;i=nxt[i]){
int v=to[i]; if (!same(i,lste)&&mark[v]&&vis[v]<2)getW(v,dd+dis[i],i);
}
}
int q[N];
ll solve(int k1){
int len=ring[k1].size(); ll ans=0;
for (int i=0;i<len;i++) mark[ring[k1][i]]=1;
tim=0,getW(ring[k1][0],0,0);
for (int i=1;i<=len;i++){
int x=id[i];
mxdp=0,DP(x,0),ans=max(ans,mxdp);
a[i]=dp[x];
}
for (int i=1;i<=len;i++) a[i+len]=a[i];
int l=1,r=1; q[l]=1;
for (int i=2;i<=tim;i++){
while (l<=r&&i-q[l]>=len)l++;
int j=q[l]; if (l<=r)ans=max(ans,a[i]+a[j]+b[i]-b[j]);
while (l<=r&&a[i]-b[i]>a[q[r]]-b[q[r]])r--;
q[++r]=i;
}
return ans;
}
int main(){
int n;read(n);
for (int i=1;i<=n;i++){
int x;ll w; read(x),read(w);
addedge(x,i,w);
}
for (int i=1;i<=n;i++) if (!dep[i])dfs(i,1,0,0);
ll ans=0;
for (int i=1;i<=tot;i++)ans+=solve(i);
printf("%lld
",ans);
return 0;
}