[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=1791
[算法]
不难看出，要求的是这个基环树森林中每棵基环树的直径之和
[代码]
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + ; struct edge
{
int to,w,nxt;
} e[MAXN << ]; int i,v,w,tot,n,u,cnt;
int degree[MAXN],belong[MAXN],head[MAXN];
long long d[MAXN],f[MAXN],a[MAXN << ],sum[MAXN << ];
long long ans;
bool cal[MAXN]; inline void addedge(int u,int v,int w)
{
tot++;
e[tot] = (edge){v,w,head[u]};
head[u] = tot;
}
inline void bfs(int u,int t)
{
int i,cur,v,w;
queue< int > q;
belong[u] = t;
q.push(u);
while (!q.empty())
{
cur = q.front();
q.pop();
for (i = head[cur]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (!belong[v])
{
belong[v] = t;
q.push(v);
}
}
}
}
inline void topsort()
{
int i,u,v,w;
queue< int > q;
for (i = ; i <= n; i++)
{
if (degree[i] == )
q.push(i);
}
while (!q.empty())
{
u = q.front();
q.pop();
for (i = head[u]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (degree[v] > )
{
d[belong[u]] = max(d[belong[u]],f[u] + f[v] + w);
f[v] = max(f[v],f[u] + w);
if ((--degree[v]) == ) q.push(v);
}
}
}
}
inline void dp(int t,int x)
{
long long i,l,r,y = x,m = ,v,w;
static int q[MAXN << ];
do
{
a[++m] = f[y];
degree[y] = ;
for (i = head[y]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (degree[v] > )
{
y = v;
sum[m + ] = sum[m] + w;
break;
}
}
} while(i);
if (m == )
{
l = ;
for (i = head[y]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (v == x) l = max(l,w);
}
d[t] = max(d[t],f[x] + f[y] + l);
return;
}
for (i = head[y]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (v == x)
{
sum[m + ] = sum[m] + w;
break;
}
}
for (i = ; i < m; i++)
{
a[m + i] = a[i];
sum[m + i] = sum[m + ] + sum[i];
}
q[l = r = ] = ;
for (i = ; i <= * m - ; i++)
{
while (l <= r && i - q[l] >= m) l++;
d[t] = max(d[t],a[q[l]] + a[i] + sum[i] - sum[q[l]]);
while (l <= r && a[q[r]] - sum[q[r]] <= a[i] - sum[i]) r--;
q[++r] = i;
}
}
int main()
{ scanf("%d",&n);
for (u = ; u <= n; u++)
{
scanf("%d%d",&v,&w);
addedge(u,v,w);
addedge(v,u,w);
degree[u]++; degree[v]++;
}
for (i = ; i <= n; i++)
{
if (!belong[i])
bfs(i,++cnt);
}
topsort();
for (i = ; i <= n; i++)
{
if (degree[i] > && !cal[belong[i]])
{
cal[belong[i]] = true;
dp(belong[i],i);
ans += d[belong[i]];
}
}
printf("%lld\n",ans); return ; }