[题解]P4381 [IOI2008]Island

· · 题解

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;
}