lessons/参考实现/09-基环树/CodeForces-835F.cpp

#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
constexpr int64 NEG = numeric_limits<int64>::min() / 4;

struct Summary {
    int64 left = NEG;
    int64 right = NEG;
    int64 best = NEG;
};

Summary combine(const Summary &a, const Summary &b) {
    if (a.left == NEG) return b;
    if (b.left == NEG) return a;
    return {max(a.left, b.left), max(a.right, b.right),
            max({a.best, b.best, a.left + b.right})};
}

struct SegmentTree {
    int size = 1;
    vector<Summary> tree;
    explicit SegmentTree(const vector<Summary> &values) {
        while (size < static_cast<int>(values.size())) size <<= 1;
        tree.assign(2 * size, {});
        for (int i = 0; i < static_cast<int>(values.size()); ++i) tree[size + i] = values[i];
        for (int i = size - 1; i > 0; --i) tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
    }
    Summary query(int left, int right) const {
        Summary before, after;
        for (left += size, right += size; left < right; left >>= 1, right >>= 1) {
            if (left & 1) before = combine(before, tree[left++]);
            if (right & 1) after = combine(tree[--right], after);
        }
        return combine(before, after);
    }
};

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

    int n;
    cin >> n;
    struct Edge { int to; int64 weight; };
    vector<vector<Edge>> graph(n);
    vector<int> degree(n, 0);
    for (int i = 0; i < n; ++i) {
        int u, v;
        int64 w;
        cin >> u >> v >> w;
        --u; --v;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
        ++degree[u]; ++degree[v];
    }
    queue<int> leaves;
    vector<char> on_cycle(n, true);
    for (int i = 0; i < n; ++i) if (degree[i] == 1) leaves.push(i);
    while (!leaves.empty()) {
        int v = leaves.front(); leaves.pop();
        on_cycle[v] = false;
        for (const Edge &edge : graph[v]) {
            if (--degree[edge.to] == 1) leaves.push(edge.to);
        }
    }

    vector<int64> height(n, 0);
    vector<int> parent(n, -2);
    int64 tree_diameter = 0;
    for (int root = 0; root < n; ++root) {
        if (!on_cycle[root]) continue;
        vector<pair<int, int>> order;
        vector<int> stack{root};
        parent[root] = -1;
        while (!stack.empty()) {
            int v = stack.back(); stack.pop_back();
            order.push_back({v, parent[v]});
            for (const Edge &edge : graph[v]) {
                if (on_cycle[edge.to] || edge.to == parent[v]) continue;
                parent[edge.to] = v;
                stack.push_back(edge.to);
            }
        }
        for (int index = static_cast<int>(order.size()) - 1; index >= 0; --index) {
            int v = order[index].first;
            int64 first = 0, second = 0;
            for (const Edge &edge : graph[v]) {
                if (on_cycle[edge.to] || parent[edge.to] != v) continue;
                int64 candidate = height[edge.to] + edge.weight;
                if (candidate > first) { second = first; first = candidate; }
                else if (candidate > second) second = candidate;
            }
            height[v] = first;
            tree_diameter = max(tree_diameter, first + second);
        }
    }

    int start = find(on_cycle.begin(), on_cycle.end(), true) - on_cycle.begin();
    vector<int> cycle;
    vector<int64> next_weight;
    int previous = -1, current = start;
    do {
        cycle.push_back(current);
        int next = -1;
        int64 weight = 0;
        for (const Edge &edge : graph[current]) {
            if (on_cycle[edge.to] && edge.to != previous) {
                next = edge.to;
                weight = edge.weight;
                break;
            }
        }
        next_weight.push_back(weight);
        previous = current;
        current = next;
    } while (current != start);

    int k = cycle.size();
    vector<int64> coordinate(2 * k, 0);
    for (int i = 1; i < 2 * k; ++i) {
        coordinate[i] = coordinate[i - 1] + next_weight[(i - 1) % k];
    }
    vector<Summary> values(2 * k);
    for (int i = 0; i < 2 * k; ++i) {
        int64 h = height[cycle[i % k]];
        values[i] = {h - coordinate[i], h + coordinate[i], NEG};
    }
    SegmentTree segment(values);
    int64 best_cycle_path = numeric_limits<int64>::max();
    for (int cut = 0; cut < k; ++cut) {
        best_cycle_path = min(best_cycle_path, segment.query(cut, cut + k).best);
    }
    cout << max(tree_diameter, best_cycle_path) << '\n';
    return 0;
}