题意
给出一个基环森林，求所有基环树的直径之和。
点数 $N\le 10^6$ 。
题解
思想
先考虑求一个基环树的直径。
设 $\text{f[i]}$ 是 $i$ 向环外延伸的最长距离，直径有两种情况：
- 不经过环，答案为环的子树直径，即 $\mathrm{max}(\text{f[x]}+\text{f[y]}+w)$ ，其中 $x,y$ 是子树中两点，$w$ 是两点距离。
- 经过环，则答案为 $\mathrm{max}(\text{f[x]}+\text{f[y]}+\mathrm{len}(x,y))$ ，其中 $x,y$ 是环上两点，$\mathrm{len(x,y)}$ 是两点在环上的较长距离。
对于情况 $2$ ，直接 $O(n^2)$ 枚举肯定会爆，考虑断环成链后用单调队列优化。
将环断成原来的两倍长，从任意一个点出发，用 $\text{s[i]}$ 表示第 $i$ 个点，设编号为 $p$ ，的 $\text{f[p]}$ 值 ；用 $\text{dis[i]}$ 代表 $i$ 距离起点的距离。答案化为
$$s[x]+s[y]+dis[y]-dis[x]\tag{1}$$
枚举 $y$ ，去除已知量后答案化为
$$s[x]-dis[x]\tag{2}$$
要求 $(2)$ 最大 ，用单调队列维护就行了。
最后对于每个子树，对两种情况取最大值相加即可。
实现
- 先用 $\text{dfs}$ 求出每个点 $i$ 所属的子树 $\text{scc[i]}$ 。
- 拓扑排序找环，还可以用树形dp顺便求出 $\text{f[i]}$ 和上述情况 $1$ 。
- 从任意一个在环上的点出发断环成链，注意还需要找终点到起点的边。完成后将子树标记，$vis[scc[x]]=1$ 。
- 用单调队列求出情况 $(2)$ 的答案。注意两个点成环的重边情况需要单独考虑。
- 开
long long。
代码
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
struct Edge {
ll next,to,w;
} edge[N<<1];
bool vis[N];
ll cnt,head[N],n,a,b,ans,scnt,scc[N],deg[N],mx[N],f[N],s[N],dis[N];
inline void add(ll u,ll v,ll w); //加边
void dfs(ll x); //dfs划分子树
inline void t_sort(); //拓扑排序，处理情况1
inline void dp(ll x); //处理情况2
signed main()
{
n=read();
for (ll i=1;i<=n;i++)
{
a=read(); b=read();
add(i,a,b);
add(a,i,b);
deg[i]++; deg[a]++; //度数
}
for (ll i=1;i<=n;i++) //划分子树
{
if (scc[i]) continue;
scnt++;
dfs(i);
}
t_sort();
for (ll i=1;i<=n;i++)
{
if (!deg[i] || vis[scc[i]]) continue; //不在环上或该子树被访问过则跳过
dp(i);
ans+=mx[scc[i]]; //统计答案
}
return !printf("%lld",ans);
}
inline void add(ll u,ll v,ll w)
{
edge[++cnt].to=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt;
}
void dfs(ll x) //划分子树
{
scc[x]=scnt;
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to;
if (scc[y]) continue;
dfs(y);
}
}
inline void t_sort() //拓扑排序
{
queue <ll> q;
for (ll i=1;i<=n;i++)
{
if (deg[i]>1) continue;
q.push(i); //不在环上入队
}
while (!q.empty())
{
ll x=q.front(); q.pop();
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to,w=edge[i].w;
if (!deg[y]) continue; //父节点跳过
mx[scc[x]]=max(mx[scc[x]],f[x]+f[y]+w);
f[y]=max(f[y],f[x]+w); //树形dp
deg[x]--; deg[y]--;
if (deg[y]==1) q.push(y);
}
}
}
inline void dp(ll x)
{
ll st=x,id=scc[x],pcnt=0; //pcnt为环上点的个数
vis[id]=1; //标记已处理过
for (;;)
{
s[++pcnt]=f[x];
deg[x]=0; //标记访问过
bool flag=0; //flag表示还有下一个点
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to,w=edge[i].w;
if (!deg[y]) continue; //不在环上或访问过
flag=1;
dis[pcnt+1]=dis[pcnt]+w;
x=y;
break;
}
if (!flag) break; //没有下一个点了退出
}
if (pcnt==2) //单独处理两点成环的情况
{
ll res=0;
for (ll i=head[x];i;i=edge[i].next)
{
ll y=edge[i].to,w=edge[i].w;
if (y!=st) continue;
res=max(res,w);
}
mx[id]=max(mx[id],f[st]+f[x]+res);
}
for (ll i=head[x];i;i=edge[i].next) //从终点到起点
{
ll y=edge[i].to,w=edge[i].w;
if (y!=st) continue;
dis[pcnt+1]=dis[pcnt]+w;
break;
}
for (ll i=1;i<pcnt;i++) //扩成两倍
{
s[i+pcnt]=s[i];
dis[i+pcnt]=dis[1+pcnt]+dis[i];
}
deque <ll> q;
q.emplace_back(1);
for (ll i=2;i<(pcnt<<1);i++) //单调队列得到答案
{
while (!q.empty() && i-q.front()>=pcnt) q.pop_front();
if (!q.empty()) mx[id]=max(mx[id],s[i]+s[q.front()]+dis[i]-dis[q.front()]);
while (!q.empty() && s[q.back()]-dis[q.back()]<=s[i]-dis[i]) q.pop_back();
q.emplace_back(i);
}
}