IOI '08 P2 - Islands (316.16 MB)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

vector<vector<pair<int, int>>> g;
vector<vector<int>> edgeId;

// DFS to find cycle
vector<bool> inPath;
vector<pair<int, int>> path; // node, weight from previous node
bool dfsCycle(int node, int parentEdge = 0) {
    if (inPath[node]) return true;
    inPath[node] = true;
    for (size_t i = 0; i < g[node].size(); ++i) {
        auto [child, w] = g[node][i];
        int e = edgeId[node][i];
        if (e != parentEdge) {
            path.emplace_back(child, w);
            if (dfsCycle(child, e)) return true;
            path.pop_back();
        }
    }
    inPath[node] = false;
    return false;
}

// DFS to mark as seen
vector<bool> seen;
void dfsComponent(int node) {
    seen[node] = true;
    for (auto [child, w] : g[node]) {
        if (!seen[child]) dfsComponent(child);
    }
}

// DFS to find max path length without moving to any banned nodes (may start at a banned node)
vector<bool> bannedNode; // (on cycle)
pair<long long, long long> findMaxPath(int node, int parent = 0) { // (max path starting here, max path in subtree)
    vector<long long> biggestPathsStartingHere;
    long long maxPathFromNode = 0, maxPathInSubtree = 0;
    for (auto [child, w] : g[node]) {
        if (child == parent || bannedNode[child]) continue;
        auto [a, b] = findMaxPath(child, node);
        a += w;
        maxPathFromNode = max(maxPathFromNode, a);
        maxPathInSubtree = max(maxPathInSubtree, b);
        biggestPathsStartingHere.push_back(a);
        sort(biggestPathsStartingHere.rbegin(), biggestPathsStartingHere.rend());
        if (biggestPathsStartingHere.size() > 2) biggestPathsStartingHere.pop_back();
    }
    long long newPath = 0;
    if (biggestPathsStartingHere.size() == 1) newPath = biggestPathsStartingHere[0];
    else if (!biggestPathsStartingHere.empty()) newPath = biggestPathsStartingHere[0] + biggestPathsStartingHere[1];
    maxPathInSubtree = max(maxPathInSubtree, newPath);
    return {maxPathFromNode, maxPathInSubtree};
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n; cin >> n;
    g.resize(1+n), edgeId.resize(1+n);
    for (int u = 1; u <= n; ++u) {
        int v, w; cin >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
        edgeId[u].push_back(u);
        edgeId[v].push_back(u);
    }

    // treat components separately
    long long totalW = 0;
    inPath.resize(1+n), seen.resize(1+n), bannedNode.resize(1+n);
    for (int r = 1; r <= n; ++r) {
        if (seen[r]) continue;

        // Mark component as seen
        dfsComponent(r);

        // Find cycle
        path.clear();
        path.emplace_back(r, 0);
        dfsCycle(r);
        vector<pair<int, int>> cycle;
        int last = path.back().first;
        int cur = (int)path.size()-1;

        do {
            cycle.push_back(path[cur--]);
        } while (path[cur].first != last);
        reverse(cycle.begin(), cycle.end());
        int m = cycle.size();
        for (auto [node, w] : cycle) bannedNode[node] = true;

        // Find longest path in each direction from the cycle
        long long maxPath = 0;
        vector<long long> pathFrom(m);
        for (int i = 0; i < m; ++i) {
            auto [pathFromI, subtreePath] = findMaxPath(cycle[i].first);
            maxPath = max(maxPath, subtreePath);
            pathFrom[i] = pathFromI;
        }

        // Try combining pairs of paths leaving the cycle
        long long S = 0;
        for (int i = 0; i < m; ++i) S += cycle[i].second;

        long long mxSum = -INF, mxDif = -INF; // max path + prefix, max path - prefix, over all j considered so far
        long long prefix = 0;
        for (int j = 0; j < m; ++j) {
            long long path = pathFrom[j];
            prefix += cycle[j].second;

            // i to j clockwise
            long long a = path + prefix + mxDif;
            // j to i clockwise
            long long b = S + path - prefix + mxSum;
            maxPath = max({maxPath, a, b});

            mxSum = max(mxSum, path+prefix);
            mxDif = max(mxDif, path-prefix);
        }

        totalW += maxPath;
    }
    cout << totalW << endl;
    return 0;
}