所以我们得把环找出来。
同时求出：从每个环上节点出发在不经过环的前提下的最长链。
这里当然借鉴一下网上大佬得拓扑排序找环辣！
于是这个玩意直接丢给拓扑排序就好。
用求树的直径的方法更新答案处理第一种情况。
对于第二种情况，就等价于从环上找出两点$i,j$使得$dp[i]+dis(i,j)+dp[j]$最大。
$dis(i,j)$为两点在环上的最长距离。
$dp[i]$表示以$i$为根的子树内以一个端点为根的最长链。
记得考虑顺时针和逆时针两种走法。
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 1000010
using namespace std;
int n,c=1,T=0;
int head[MAXN],degree[MAXN],colour[MAXN],que[MAXN<<1];
long long ans=0,dis[MAXN],dp[MAXN],f[MAXN<<1],g[MAXN<<1];
bool vis[MAXN];
struct Edge{
int next,to,w;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
inline void add(int u,int v,int w){
a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;
degree[u]++;degree[v]++;
}
void bfs(int rt){
int l=1,r=1,u,v;
que[1]=rt;
colour[rt]=T;
while(l<=r){
u=que[l];
for(int i=head[u];i;i=a[i].next){
v=a[i].to;
if(!colour[v]){
que[++r]=v;
colour[v]=T;
}
}
l++;
}
}
void topsort(){
int l=1,r=0,u,v;
for(int i=1;i<=n;i++)if(degree[i]==1)que[++r]=i;
while(l<=r){
u=que[l];
for(int i=head[u];i;i=a[i].next){
v=a[i].to;
if(degree[v]>1){
dis[colour[u]]=max(dis[colour[u]],dp[u]+dp[v]+a[i].w);
dp[v]=max(dp[v],dp[u]+a[i].w);
degree[v]--;
if(degree[v]==1)que[++r]=v;
}
}
l++;
}
}
void solve(int rt,int colour){
int u,v,m=0;
u=rt;
for(int i=1;i;){
f[++m]=dp[u];
degree[u]=1;
for(i=head[u];i;i=a[i].next){
v=a[i].to;
if(degree[v]>1){
g[m+1]=g[m]+a[i].w;
u=v;
break;
}
}
}
if(m==2){
int len=0;
for(int i=head[u];i;i=a[i].next)if(a[i].to==rt)len=max(len,a[i].w);
dis[colour]=max(dis[colour],dp[rt]+dp[u]+len);
}
else{
int l=1,r=1;
que[1]=1;
for(int i=head[u];i;i=a[i].next)if(a[i].to==rt){
g[m+1]=g[m]+a[i].w;
break;
}
for(int i=1;i<m;i++){
f[m+i]=f[i];
g[m+i]=g[m+1]+g[i];
}
for(int i=2;i<2*m;i++){
while(l<=r&&i-que[l]>=m)l++;
dis[colour]=max(dis[colour],f[i]+f[que[l]]+g[i]-g[que[l]]);
while(l<=r&&f[que[r]]-g[que[r]]<=f[i]-g[i])r--;
que[++r]=i;
}
}
}
void work(){
for(int i=1;i<=n;i++)if(degree[i]>1&&!vis[colour[i]]){
vis[colour[i]]=true;
solve(i,colour[i]);
ans+=dis[colour[i]];
}
printf("%lld\n",ans);
}
void init(){
int x,w;
n=read();
for(int i=1;i<=n;i++){
x=read();w=read();
add(i,x,w);
}
for(int i=1;i<=n;i++)if(!colour[i]){T++;bfs(i);}
topsort();
}
int main(){
init();
work();
return 0;
}
原文：https://www.cnblogs.com/Yangrui-Blog/p/10500076.html