Island

 

https://www.luogu.com.cn/problem/P4381

题意

有 $n$ 个点,每个点 $i$ 都有一条出发到 $a_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

alt

我们可以将其变形为这样

alt

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

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

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

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

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

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

10 6 5 15 8 11 3
dep 23 1 1 102 0 0 11
len 3 2 54 3 10 78 23

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#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;
}
algorithm