1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define W while #define I inline #define RI register int #define LL long long #define Cn const #define CI Cn int& #define gc getchar #define D isdigit(c=gc()) #define pc(c) putchar((c)) #define min(x,y) ((x)<(y)?(x):(y)) #define max(x,y) ((x)>(y)?(x):(y)) using namespace std; namespace Debug{ Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;} Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);} Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;} #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__) }using namespace Debug; namespace FastIO{ Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;} Ts I void read(Ty& x,Ar&... y){read(x),read(y...);} Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);} Tp I void writeln(Cn Ty& x){write(x),pc('\n');} }using namespace FastIO; Cn int N=131072+10; int n;LL CUR; #define to son[i] #define pa pair<LL,LL> #define mp make_pair #define fi first #define se second vector<pa> v[N],g,G[N]; #define pb push_back I void DFS(CI x,CI fa){ if(v[x].clear(),G[x].empty()) return v[x].pb(mp(0,0)),void(); LL t;RI k,i,j,ls,rs,sl,sr;for(auto i:G[x]) DFS(i.fi,x); for(g.clear(),k=0;k<2;k++) for(ls=G[x][k].fi,rs=G[x][k^1].fi,t=CUR-G[x][0].se-G[x][1].se,sl=v[ls].size(),sr=v[rs].size(),i=0,j=0;i<sl;i++){ W(j+1<sr&&v[rs][j+1].fi<=t-v[ls][i].se) ++j; j<sr&&v[rs][j].fi<=t-v[ls][i].se&&(g.pb({v[ls][i].fi+G[x][k].se,v[rs][j].se+G[x][k^1].se}),0); }sort(g.begin(),g.end());for(auto i:g) (v[x].empty()||i.se<v[x].back().se)&&(v[x].pb(i),0); } int main(){ RI i,j,x,y,z;LL l=0,r=0,mid,X;for(read(n),i=2;i<=n;i++) read(x,z),G[x].pb({i,z}),r+=z;srand(time(NULL)); W(l<=r) CUR=mid=l+r>>1,DFS(1,0),!v[1].empty()?X=mid,r=mid-1:l=mid+1; return writeln(X),0; }
|