Submission #1613626

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = (1<<17) + 5;

ll st, dr, mid;
int dad, cost, i, n, son[Nmax][2], edge[Nmax][2];

vector< pair<ll, ll> > solve(int node, ll val)
{
    if(!son[node][0])
    {
        vector< pair<ll, ll> > ans;
        ans.push_back({0, 0});
        return ans;
    }

    auto a = solve(son[node][0], val), b = solve(son[node][1], val);
    vector< pair<ll, ll> > v1, v2;
    if(a.size() > b.size()) swap(a, b);

    val -= edge[node][0] + edge[node][1];

    int i, j;
    j = 0;
    for(i = 0; i < a.size(); ++i)
    {
        while(j < b.size() && a[i].second + b[j].first <= val) ++j;
        if(j && !(v1.size() && v1.back().second == b[j-1].second + edge[node][1]))
            v1.push_back({ a[i].first + edge[node][0], b[j-1].second + edge[node][1] });
    }

    j = 0;
    for(i = 0; i < a.size(); ++i)
    {
        while(j < b.size() && a[i].first + b[j].second > val) ++j;
        if(j < b.size())
        {
            if(v2.size() && v2.back().first == b[j].first + edge[node][1]) v2.back().second = a[i].second + edge[node][0];
                else v2.push_back({ b[j].first + edge[node][1], a[i].second + edge[node][0] });
        }
    }

    vector< pair<ll, ll> > ans;
    i = 0; j = 0;
    ll best = (ll) Nmax * Nmax;

    while(i < v1.size() && j < v2.size())
    {
        if(v1[i] < v2[j])
        {
            ans.push_back(v1[i]);
            best = min(best, v1[i++].second);
            while(j < v2.size() && v2[j].second >= best) ++j;
        }
        else
        {
            ans.push_back(v2[j]);
            best = min(best, v2[j++].second);
            while(i < v1.size() && v1[i].second >= best) ++i;
        }
    }

    while(i < v1.size()) ans.push_back(v1[i++]);
    while(j < v2.size()) ans.push_back(v2[j++]);

    return ans;
}

int main()
{
 //   freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=2; i<=n; ++i)
    {
        cin >> dad >> cost;
        if(son[dad][0]) son[dad][1] = i, edge[dad][1] = cost;
            else son[dad][0] = i, edge[dad][0] = cost;
    }

    st = 0; dr = (ll)Nmax * Nmax;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(solve(1, mid).empty()) st = mid + 1;
            else dr = mid - 1;
    }

    cout << st << '\n';
    return 0;
}

Submission Info

Judge Result