BZOJ1791或洛谷4381 [IOI2008]Island

一道基环树的直径

BZOJ原题链接

洛谷原题链接

又是一道实现则麻烦的题。。

显然公园其实是基环树森林，求的最长距离其实就是求每一棵基环树的直径的总和。
对于每棵基环树，其直径要么经过环，要么是某个环上点的子树的直径。所以我们可以先找出它的环，然后对环上的每个点进行\(dfs\)（不能经过环上的点），找出该点的子树的直径和数组\(D\)，表示该点到子树中的叶子节点的最大距离。
然后考虑经过环的距离，设当前枚举到两个点\(x,y\)，则长度为\(D[x]+D[y]+dis(x,y)\)，这个可以通过单调队列来优化，维护一个最大值即可。

#include<cstdio>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int fi[N], di[N << 1], da[N << 1], ne[N << 1], cr[N], cr_d[N], q[N << 1], po[N << 1], l, cb, fp, n;
ll D[N], dis[N << 1], fr;
bool v[N], egv[N << 1], vis[N];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c<'0' || c>'9'; c = getchar())
        p |= c == '-';
    for (; c >= '0'&&c <= '9'; c = getchar())
        x = x * 10 + (c - '0');
    return p ? -x : x;
}
inline void add(int x, int y, int z)
{
    di[++l] = y;
    da[l] = z;
    ne[l] = fi[x];
    fi[x] = l;
}
inline ll maxn(ll x, ll y)
{
    return x > y ? x : y;
}
void dfs(int x)
{
    int i, y;
    v[x] = 1;
    for (i = fi[x]; i; i = ne[i])
    {
        y = di[i];
        if (!egv[i])
        {
            cr[y] = x;
            cr_d[y] = da[i];
            egv[i] = egv[i & 1 ? i + 1 : i - 1] = 1;
            if (v[y])
                cb = y;
            dfs(y);
        }
    }
}
void dfs_2(int x, ll d, int fa)
{
    int i, y;
    if (fr < d)
    {
        fr = d;
        fp = x;
    }
    for (i = fi[x]; i; i = ne[i])
    {
        y = di[i];
        if (!vis[y] && y != fa)
        {
            dfs_2(y, d + da[i], x);
            D[x] = maxn(D[x], D[y] + da[i]);
        }
    }
}
void dfs_3(int x, ll d, int fa)
{
    int i, y;
    fr = maxn(fr, d);
    for (i = fi[x]; i; i = ne[i])
    {
        y = di[i];
        if (!vis[y] && y != fa)
            dfs_3(y, d + da[i], x);
    }
}
int main()
{
    int i, j, x, y, k, head, tail;
    ll s = 0, ma;
    n = re();
    for (i = 1; i <= n; i++)
    {
        x = re();
        y = re();
        add(i, x, y);
        add(x, i, y);
    }
    for (i = 1; i <= n; i++)
        if (!v[i])
        {
            ma = 0;
            dfs(i);
            j = cb;
            k = 0;
            do
            {
                vis[j] = 1;
                k++;
                dis[k + 1] = dis[k] + cr_d[j];
                po[k] = j;
                j = cr[j];
            } while (j^cb);
            do
            {
                vis[j] = 0;
                fr = 0;
                dfs_2(j, 0, 0);
                fr = 0;
                dfs_3(fp, 0, 0);
                vis[j] = 1;
                ma = maxn(ma, fr);
                k++;
                dis[k + 1] = dis[k] + cr_d[j];
                po[k] = j;
                j = cr[j];
            } while (j^cb);
            head = 1;
            tail = 0;
            for (j = 1; j <= k; j++)
            {
                while (j - q[head] >= (k >> 1))
                    head++;
                if (head <= tail)
                    ma = maxn(ma, D[po[j]] + D[po[q[head]]] + dis[j] - dis[q[head]]);
                else
                    ma = maxn(ma, D[po[j]]);
                while (head < tail&&D[po[j]] - dis[j] >= D[po[q[tail]]] - dis[q[tail]])
                    tail--;
                q[++tail] = j;
            }
            s += ma;
        }
    printf("%lld", s);
    return 0;
}

ps：因为我用的是\(VS\)，所以代码会自动补空格，而我本来的风格是没有空格的。

BZOJ1791或洛谷4381 [IOI2008]Island

原文：https://www.cnblogs.com/Iowa-Battleship/p/9600841.html