Submission #980851

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VVI cd,cl;
const in inf=1e15;
in tt;
in bv(in u, in lf){
  if(lf<0)
    return inf;
  if(sz(cd[u])==0)
    return 0;
  assert(sz(cd[u])==2);
  in bst=inf;
  in a;
  forn(z,2){
    a=bv(cd[u][z],lf-cl[u][z])+cl[u][z];
    a=bv(cd[u][!z],tt-(a+cl[u][!z]))+cl[u][!z];
    bst=min(bst,a);
  }
  return bst;
}
bool isp(in mx){
  tt=mx;
  in a=bv(cd[0][0],inf)+cl[0][0];
  a=bv(cd[0][1],tt-(a+cl[0][1]))+cl[0][1];
  if(a<inf)
    return 1;
  return 0;
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n;
  cin>>n;
  cd.resize(n);
  cl.resize(n);
  in a,v;
  forn(i,n-1){
    cin>>a>>v;
    cd[a-1].PB(i+1);
    cl[a-1].PB(v);
  }
  in mn=-1;
  in mx=inf;
  in md;
  while(mx-mn>1){
    md=(mx+mn)/2;
    if(isp(md))
      mx=md;
    else
      mn=md;
  }
  cout<<mx<<endl;
  return 0;
}

Submission Info

Judge Result