P4381 Island

题意

有 $nn$ 个点，每个点 $ii$ 都有一条出发到 $a_{i}a\_i$ 的边有权值 $w_{i}w\_i$ 。

求这些点形成的基环树他们的直径之和。

思路

对于这样的一个基环树

11 3 23
15 8 10
7 12 9
7 1 3
10 6 2
5 15 3
2 5 1
15 1 90
14 3 11
10 4 23
11 8 78
13 1 12
6 5 54
9 6 1
3 10 3

我们可以将其变形为这样

那么我们就得到了一个环和环上点的子树。

那么我们基环树的直径就变成了两个部分，要么是子树的最大直径，要么是环上最大长度。

对于子树最大直径不再赘述。

环上的直径如何计算呢。首先，我们计算得到所有环的子树的最大长度 dep[u]，如果没有就算 0。

那么我们要算的最大长度就是 dep[u] + dep[v] + dis(u , v)

对于一个环来说，我们可以很方便的得到点和到上一个点的距离，记为 len[u]，那么我们就得到如下的一组数了

那么剩下来的问题就是一个单调队列了。

如果不熟悉可以先看看这个题目 Loj-10178-旅行问题

我们将其破链成环，再拷贝一份到后面去，这样的话我们的长度就可以变为 dep[u] + dep[v] + |∑len[u] - ∑len[v]|。其中我们保证 u和 v 的距离不超过环的长度，且 u != v。

Code

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e6 + 10;

vector<pair<int, long long>> E[N];
int stk[N * 2];
long long len[N * 2];
int q[N * 2];
int vis[N];
int top = 0;

int s, t;

long long maxx = -1;

long long ans = 0;

bool cir(int u, int fa = -1) {
    vis[u] = true;
    int cnt = 0;
    for (auto [x, y] : E[u]) {
        if (x == fa && ++cnt < 2) continue;
        if (x == s || x == t) continue;
        if (vis[x]) {
            s = x;
            t = u;
            len[top] = y;
            stk[top++] = u;
            return true;
        }
        if (cir(x, u)) {
            len[top] = y;
            stk[top++] = u;
            if (u == s) return false;
            return true;
        }
    }

    return false;
}

long long deep[N];

void dfs(int u, int fa = -1) {
    vis[u] = true;
    long long d1, d2;
    d1 = d2 = 0;
    for (auto [x, y] : E[u]) {
        if (x == fa) continue;
        dfs(x, u);
        if (deep[x] + y >= d1) {
            d2 = d1;
            d1 = deep[x] + y;
        } else if (deep[x] + y > d2)
            d2 = deep[x] + y;
    }
    maxx = max(d1 + d2, maxx);
    deep[u] = d1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        long long j, x;
        cin >> j >> x;
        E[i].push_back({j, x});
        E[j].push_back({i, x});
    }

    long long ans = 0;

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            maxx = 0;
            top = 0;
            cir(i);
            for (int i = 0; i < top; i++) {
                long long d1 = 0, d2 = 0;
                int up = stk[(i + 1) % top];
                int dp = stk[(i + top - 1) % top];
                for (auto [x, y] : E[stk[i]]) {
                    if (x == up || x == dp) continue;
                    dfs(x, stk[i]);
                    if (deep[x] + y >= d1) {
                        d2 = d1;
                        d1 = deep[x] + y;
                    } else if (deep[x] + y > d2)
                        d2 = deep[x] + y;
                }
                maxx = max(d1 + d2, maxx);
                deep[stk[i]] = d1;
            }

            for (int i = top; i <= top * 2; i++) {
                stk[i] = stk[i - top];
                len[i] = len[i - top];
            }

            for (int i = 1; i <= top * 2; i++) {
                len[i] += len[i - 1];
            }

            for (int i = 0, head = 0, tail = -1; i <= top * 2; i++) {
                while (head <= tail && i - q[head] >= top) head++;

                if (head <= tail) {
                    int kki = stk[i];
                    int kkj = stk[q[head]];
                    maxx = max(maxx,
                               deep[kki] + len[i] + deep[kkj] - len[q[head]]);
                }

                while (head <= tail && deep[stk[q[tail]]] - len[q[tail]] <=
                                           deep[stk[i]] - len[i])
                    tail--;
                q[++tail] = i;
            }
            ans += maxx;
        }
    }

    cout << ans << '\n';

    return 0;
}