Submission #1453840

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <tuple>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cassert>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

int main() {
    int n; scanf("%d", &n);
    vector<vector<pair<int, int> > > g(n);
    repeat (i, n - 1) {
        int a, v; scanf("%d%d", &a, &v);
        g[a - 1].emplace_back(i + 1, v);
        g[i + 1].emplace_back(a - 1, v);
    }
    function<vector<tuple<ll, ll, ll> > (int, int)> dfs = [&](int i, int parent) {
        vector<tuple<ll, ll, ll> > left;
        vector<tuple<ll, ll, ll> > right;
        for (auto edge : g[i]) {
            int j, value; tie(j, value) = edge;
            if (j != parent) {
                auto x = dfs(j, i);
                auto & y = left.empty() ? left : right;
                assert (y.empty());
                y = move(x);
                repeat (i, y.size()) {
                    get<0>(y[i]) += value;
                    get<1>(y[i]) += value;
                }
            }
        }
        if (left.empty()) {
            vector<tuple<ll, ll, ll> > result;
            result.emplace_back(0, 0, 0);
            return result;
        }
        assert (not right.empty());
        vector<tuple<ll, ll, ll> > result;
        if (left.size() < right.size()) {
            left.swap(right);
        }
        for (auto l : left) {
            ll l1, l2, lmin; tie(l1, l2, lmin) = l;
            for (auto r : right) {
                ll r1, r2, rmin; tie(r1, r2, rmin) = r;
                auto push = [&](ll a, ll b, ll c) {
                    if (a < b) swap(a, b);
                    result.emplace_back(a, b, max(c, max(lmin, rmin)));
                };
                push(l1, r1, l2 + r2);
                push(l1, r2, l2 + r1);
                push(l2, r1, l1 + r2);
                push(l2, r2, l1 + r1);
            }
        }
        if (result.size() >= 1000) {
            partial_sort(result.begin() +   0, result.begin() + 150, result.end(), [&](auto x, auto y) { return get<0>(x) < get<0>(y); });
            partial_sort(result.begin() + 150, result.begin() + 300, result.end(), [&](auto x, auto y) { return get<1>(x) < get<1>(y); });
            partial_sort(result.begin() + 300, result.begin() + 700, result.end(), [&](auto x, auto y) { return get<2>(x) < get<2>(y); });
            whole(random_shuffle, result);
            result.resize(1000);
        }
        int k = result.size();
        for (int i = 0; i < k; ++ i) {
            ll i1, i2, imin; tie(i1, i2, imin) = result[i];
            bool found = false;
            repeat (j, k) if (j != i) {
                ll j1, j2, jmin; tie(j1, j2, jmin) = result[j];
                if (j1 <= i1 and j2 <= i2 and jmin <= imin) {
                    found = true;
                    break;
                }
            }
            if (found) {
                swap(result[i], result[k - 1]);
                -- i;
                -- k;
            }
        }
        result.resize(k);
        return result;
    };
    auto acc = dfs(0, -1);
    constexpr ll inf = ll(1e18)+9;
    ll result = inf;
    for (auto it : acc) {
        setmin(result, get<2>(it));
    }
    printf("%lld\n", result);
    return 0;
}

Submission Info

Judge Result