Description：

求一个基环树森林的直径和。

$1\leqslant n\leqslant10^6$

Solution：

如果做过仙人掌求直径的话那这题就很简单了，先在树上树形 $DP$ 一下，那么一个联通块的直径可能经过基环也可能不经过，不经过的话就和树形 $DP$ 一样做就行了，经过的话在环上把环复制一倍，然后有 $res=\max(f[i]+f[j]+sum[i]-sum[j])(i-j\leqslant len)$ ，发现这个可以用单调队列优化，时间复杂度 $O(n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n;

#define MAXN 1000010

struct edge

{

	int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

int fa[MAXN],d[MAXN];

int ind[MAXN];

void add(int a,int b,int c)

{

	++ind[b];

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

bool v[MAXN];

typedef long long ll;

ll f[MAXN];

int s[MAXN << 1],top = 0;

ll sumv[MAXN << 1];

int q[MAXN << 1],head,tail;

ll dia[MAXN];

ll dp(int k)

{

	top = 0;

	for(int i = k;!v[k];k = fa[k])

	{

		s[++top] = k;

		v[k] = true;

	}

	for(int i = 1;i <= top;++i)s[i + top] = s[i];

	for(int i = 1;i <= 2 * top;++i)sumv[i] = sumv[i - 1] + d[s[i - 1]];

	head = 1,tail = 0;

	ll res = 0;

	q[++tail] = 1;

	for(int i = 2;i <= 2 * top;++i)

	{

		while(head <= tail && q[head] <= i - top)++head;

		res = max(res,f[s[i]] + f[s[q[head]]] + sumv[i] - sumv[q[head]]);

		while(head <= tail && f[s[q[tail]]] - sumv[q[tail]] < f[s[i]] - sumv[i])--tail;

		q[++tail] = i;

	}

	for(int i = 1;i <= top;++i)res = max(res,dia[s[i]]);

	return res;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		fa[i] = rd();d[i] = rd();

		add(i,fa[i],d[i]);

	}

	queue<int> q;

	for(int i = 1;i <= n;++i)

		if(ind[i] == 0)q.push(i);

	ll ans = 0;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = true;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(!v[e[i].to])

			{

				--ind[e[i].to];

				dia[e[i].to] = max(dia[e[i].to],f[e[i].to] + f[k] + e[i].v);

				dia[e[i].to] = max(dia[e[i].to],dia[k]);

				f[e[i].to] = max(f[e[i].to],f[k] + e[i].v);

				if(ind[e[i].to] == 0)q.push(e[i].to);

			}

		}

	}

	for(int k = 1;k <= n;++k)

		if(!v[k])ans += dp(k);

	cout << ans << endl;

	return 0;

}