myblog

题意

给你一个基环树森林，要你求森林的直径之和(一棵基环树的直径要求点和边都不重复)

Sol

把环看成根，考虑两种情况，直径不经过根和经过根

不经过环的

不经过根的很好做，对于根的每棵子树求直径就可以了

经过环的

设$f_x$表示$x$子树中离$x$最远的点的距离，则答案便是

$$ans_1=max\left\{f_i + f_j + dis_{i,j}\right\}$$

对环上的边权前缀和一下为$dis_i$，答案变成

$$ans_1=max\left\{ f_i + f_j + dis_i - dis_j \right\}$$

整理一下

$$ans_1=max\left\{ (f_i + dis_i )+ (f_j - dis_j) \right\}$$

设环上边权总和为$len$，其实当$dis_i - dis_j < 0$时，严谨地说答案应为

$$ans2=max\left\{ (f_i + dis_i )+ (f_j - dis_j) + len \right\}$$

所以只要求一下$max\left\{ f_i + dis_i \right\}$和$max\left\{f_i - dis_i\right\}$即可

所以第二种情况的答案为$max\left\{ans_1,ans_2 \right\}$

code

代码超级简洁

#include <queue>
#include <cstdio>
#include <climits>
#include <algorithm>

typedef long long LL;
const int N = 1e6 + 30;

int n;
int to[N], w[N], in[N];
LL ans;
LL f[N], g[N];

std::queue < int > q;

int read()
{
    int ss = 0, ff = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') ss = ss * 10 + ch - '0', ch = getchar();
    return ss * ff;
}

LL get(int p)
{
    int tmp = p; p = to[p];
    LL m1 = f[tmp], m2 = f[tmp], s = w[tmp], ans1 = g[tmp], ans2 = LLONG_MIN;
    while (p != tmp)
    {
        in[p] = 0;
        ans1 = std::max(ans1, std::max(g[p], f[p] + s + m1));
        ans2 = std::max(ans2, f[p] - s + m2);
        m1 = std::max(m1, f[p] - s), m2 = std::max(m2, f[p] + s);
        s += w[p], p = to[p];
    }
    return std::max(ans1, ans2 + s);
}

int main()
{
    n = read();
    for (int i = 1; i <= n; ++i) to[i] = read(), w[i] = read(), ++ in[to[i]];
    for (int i = 1; i <= n; ++i)
        if (!in[i]) q.push(i);
    while (!q.empty())
    {
        int p = q.front(); q.pop();
        LL c = f[p] + w[p];
        g[to[p]] = std::max(g[to[p]], std::max(f[to[p]] + c, g[p]));
        f[to[p]] = std::max(f[to[p]], c);
        if (!--in[to[p]]) q.push(to[p]);
    }
    for (int i = 1; i <= n; ++i)
        if (in[i]) ans += get(i);
    printf ("%lld\n", ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
struct edge {int x, y, w, pre;}a[N<<1];int alen, last[N];
void add(int x, int y, int w){alen++;a[alen]=edge{x, y, w, last[x]};last[x]=alen;}

int n, cn, cv[N], cw[N], tsp, dfn[N], v[N], pre[N];
LL ans, d[N], A[N], B[N], C[N], D[N];
void findc(int x, int kk) 
{
	dfn[x]=++tsp;
	for(int k=last[x];k;k=a[k].pre)if(k!=(kk^1)) 
	{
		int y=a[k].y;
		if(!dfn[y]) 
		{
			pre[y]=k;
			findc(y, k);
		} 
		else if(dfn[x]<dfn[y])
		{
			for(int z=y;z!=x;z=a[pre[z]].x)
			{
				++cn;cv[cn]=z;cw[cn]=a[pre[z]].w;
				v[z]=1;
			}
			++cn;cv[cn]=x;cw[cn]=a[k].w;
			v[x]=1;
		}
	}
}
void dp(int x, int kk) 
{
	v[x]=1; 
	for(int k=last[x];k;k=a[k].pre)if(k!=(kk^1))
	{
		int y=a[k].y, w=a[k].w;
		if(!v[y]) 
		{
			dp(y, k);
			ans=max(ans, d[x]+d[y]+w);
			d[x]=max(d[x], d[y]+w);
		}
	}
}
int main() 
{

	scanf("%d", &n);
	alen=1;memset(last, 0, sizeof(last)); 
	for(int i=1, y, w; i<=n; i++) 
	{
		
		scanf("%d%d", &y, &w);
		add(i, y, w);
		add(y, i, w);
	}
	
	tsp=0;memset(dfn, 0, sizeof(dfn));
	memset(v, 0, sizeof(v));
	LL res=0;
	for(int i=1;i<=n;i++) if(!dfn[i])
	{
		cn=0;findc(i, 0);//深搜找环
		
		ans=0;for(int i=1; i<=cn; i++)dp(cv[i], 0);//深搜求直径ans
		
		LL sum=0, mx=0, cw1n=cw[cn];
		A[0]=B[0]=0;
		for(int i=1; i<=cn; i++) //求前缀
		{
			sum+=cw[i-1];if(i==1)sum=0;
			A[i]=max(A[i-1], sum+d[cv[i]]);
			B[i]=max(B[i-1], mx+d[cv[i]]+sum);
			mx=max(mx, d[cv[i]]-sum);
		}
		
		sum=mx=0;
		C[cn+1]=D[cn+