算是较难的一道基环树模板题
题意简明扼要，有一堆基环树构成了基环树森林，需求所有基环树的直径之和。
基环树定义：一棵树有$n$个节点$n$条边
显然一棵普通的树有$n$个节点$n-1$条边，那么基环树就是在普通的树的基础上多加了一条边，这条边必然会形成一个环。
所以基环树相对于树来讲就是多了一个环的处理。
基环树的直径求法：
首先肯定要找到环上的所有节点，就是相当于无向图找环。大致上常用的有拓扑排序和$dfs$，$tarjan$也可以。(我使用了$dfs$找环
$dfs$在无向图上找环比较麻烦，它只能处理环的变数$>2$的环，所以$=2$的环还要进行特判。（大体来说就是$num$从$1$开始建边这样一条边的反向边就是$i\oplus1$,这样特判一下就好了。
找到环后，通过对一些例子的手玩，不难发现基环树直径的构成情况：
$1.$就是不在环上的节点组成的最长链。
$2.$由环上两点及分别以他们为根的子树中的经过根的最长链构成。
对第一种情况我们开一个数组记录哪些点在环上，对环上每个点分别跑一遍最长链的$dp$并同时更新$answer$即可。如果他的儿子在环上就$continue$。跑完之后再开一个数组记录经过根的最长链。
(最长链$dp$就是对每个节点求出以他为根的子树且经过他的最长链和次长链，每求完一个节点的信息就对$answer$进行更新。
对于环上的两点之间的距离，可能是顺时针也可能是逆时针。所以需要破环成链，这样每个节点都会被逆时针顺时针走一遍。求出一个距离前缀数组，两点之间差值即为环上距离。
那么现在可以写出$dp$式子$answer=max(answer,d[i]+d[j]+dis[i]-dis[j])$
这个$dp$式子的与i有关和与j有关的项是独立的，所以可以单调队列优化。
对于每个节点找到他之前的$d[j]-dis[j]$最大的$j$更新即可
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
#define int long long
#define N 1000050
int head[N],num=1,n,vis[N],ins[N],stack[N],top,circle[N],cnt,flag,zongshu,huan[N],q[N*2],ooo,tmp;
ll ans,answer,dis[N*2],dp[N][2],d[N*2];
struct node
{
int next,to;
ll dis;
}edge[N*2];
void addedge(int u,int v,ll w)
{
edge[++num]=(node){head[u],v,w};
head[u]=num;
}
void dfs(int x,int fa)
{
ins[x]=1,stack[++top]=x;
for(register int i=head[x];i;i=edge[i].next)
{
if(flag)return;
int v=edge[i].to;
if(v==fa)continue;
if(ins[v])
{
flag=1;circle[++cnt]=v;huan[v]=1;
while(stack[top]!=v)
huan[stack[top]]=1,circle[++cnt]=stack[top--];
return;
}
dfs(v,x);
}
top--;ins[x]=0;
}
void dfs2(int x,int fa)
{
if(!vis[x])zongshu++,vis[x]=1;
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa)continue;
if(!vis[v])dfs2(v,x);
}
}
void dpp(int x,int fa)
{
for(int i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa || huan[v])continue;
dpp(v,x);
if(dp[v][0]+edge[i].dis>dp[x][0])
{
dp[x][1]=dp[x][0];
dp[x][0]=dp[v][0]+edge[i].dis;
}
else
if(dp[v][0]+edge[i].dis>dp[x][1])
{
dp[x][1]=dp[v][0]+edge[i].dis;
}
}
answer=max((ll)dp[x][0]+dp[x][1],answer);
}
void dfs3(int x,ll uuu)
{
dis[++ooo]=uuu;
for(int i=head[x];i;i=edge[i].next)
{
if(ooo==2*cnt)return;
int v=edge[i].to;
if(v!=q[ooo+1])continue;
dfs3(v,uuu+edge[i].dis);
}
}
void find2(int x,int fa,int last)
{
for(int i=head[x];i;i=edge[i].next)
{
if(flag)return;
int v=edge[i].to;
if(v==fa && i!=last && i!=(last^1))
{
circle[++cnt]=x;
circle[++cnt]=fa;
huan[x]=huan[fa]=1;flag=1;
tmp=max(edge[i].dis,edge[last].dis);
}
else if(v!=fa)find2(v,x,i);
}
}
ll solve(int root)
{
zongshu=0;
dfs2(root,0);
if(zongshu==2)
{
answer=0;
for(int i=head[root];i;i=edge[i].next)answer=max(answer,edge[i].dis);
return answer;
}
for(int i=1;i<=n;i++)stack[i]=0,ins[i]=0;
flag=top=cnt=answer=0;
dfs(root,0);
if(cnt==0)
{
flag=0;
tmp=0;
find2(root,0,-1);
for(int i=1;i<=cnt;i++)dpp(circle[i],0),d[circle[i]]=dp[circle[i]][0];
answer=max(answer,tmp+d[circle[1]]+d[circle[2]]);
return answer;
}
ooo=0;
for(int i=1;i<=cnt;i++)dpp(circle[i],0),d[circle[i]]=dp[circle[i]][0];
for(int i=1;i<=cnt;i++)q[i]=circle[i],q[i+cnt]=circle[i],circle[i+cnt]=circle[i];
dfs3(q[1],0);
int head=0,tail=1;
q[++head]=1;
for(int i=2;i<=2*cnt;i++)
{
while(head<=tail && q[head]<=i-cnt)head++;
answer=max(answer,d[circle[i]]+d[circle[q[head]]]+dis[i]-dis[q[head]]);
while(head<=tail && d[circle[i]]-dis[i]>=d[circle[q[tail]]]-dis[q[tail]])tail--;q[++tail]=i;
}
return answer;
}
signed main()
{
freopen("random.out","r",stdin);
freopen("myanswer.out","w",stdout);
scanf("%lld",&n);
int u;ll v;
for(int i=1;i<=n;i++)scanf("%lld%lld",&u,&v),addedge(i,u,v),addedge(u,i,v);
for(int i=1;i<=n;i++)if(!vis[i])ans+=solve(i);
printf("%lld",ans);
return 0;
}这应该是这道题最丑最长的一份代码，为了求环跑了一遍dfs，为了标记跑了一遍dfs，为了求前缀和又跑了一遍dfs，特判还有一遍dfs
