Submission #3217042

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=1<<17|3;
struct PI{
	ll in,out;
};
inline PI mp(ll a,ll b){
	return (PI){a,b};
}
bool operator < (PI a,PI b){
	return a.in<b.in;
}
int n,ch[N][2];
ll dep[N],lim;
vector<PI> dp[N];
vector<PI> Merge(vector<PI> &a,vector<PI> &b){
	vector<PI> v,ans; v.clear(); ans.clear();
	v.resize(a.size()+b.size());
	merge(a.begin(),a.end(),b.begin(),b.end(),v.begin());
	for(auto i:v)if(ans.size()==0||i.out<ans[ans.size()-1].out)ans.push_back(i);
	return ans;
}
vector<PI> Merge(ll lim,vector<PI> &a,vector<PI> &b){
	vector<PI> v; v.clear();
	if(!a.size()||!b.size())return v;
	unsigned j=0;
	for(auto i:a){
		while(j+1<b.size()&&b[j+1].in+i.out<=lim)j++;
		//if(lim==23)cout<<i.in<<"dasfas  "<<b[j].out<<endl;
		if(b[j].in+i.out<=lim)v.push_back(mp(i.in,b[j].out));
	}
	return v;
}
void solve(int p){
	if(!ch[p][0]){
		dp[p].push_back(mp(dep[p],dep[p]));
		return;
	}
	solve(ch[p][0]); solve(ch[p][1]);
	vector<PI> tmp1=Merge(lim+dep[p]*2,dp[ch[p][0]],dp[ch[p][1]]);
	vector<PI> tmp2=Merge(lim+dep[p]*2,dp[ch[p][1]],dp[ch[p][0]]);
	dp[p]=Merge(tmp1,tmp2);
	//cout<<p<<" cqz "<<dp[p].size()<<endl;
	//for(auto i:dp[p])cout<<i.in<<" "<<i.out<<endl;
}
bool check(){
	solve(1); 
	if(dp[1].size())return 1;
	//for(auto i:dp[1])if(i.in+i.out<=lim)return 1;
	return 0;
}
int main(){
	n=read();
	for(int i=2;i<=n;i++){
		int fa=read(),v=read();
		dep[i]=dep[fa]+v;
		if(ch[fa][0])ch[fa][1]=i; else ch[fa][0]=i;
	}
	//lim=15; cout<<check()<<endl; return 0;
	ll l=0,r=((ll)1<<34)-10;
	while(l<r){
		lim=(l+r)>>1;
		if(check())r=lim; else l=lim+1;
	}
	cout<<l<<endl;
}

Submission Info

Judge Result