Submission #1692904

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 131072
int n,l[MN+5],r[MN+5];
ll d[MN+5];
vector< pair<ll,ll> > v[MN+5],V;
bool check(ll x)
{
	for(int i=n;i;--i)
	{
		v[i].clear();V.clear();
		if(!l[i]){v[i].push_back(make_pair(d[i],d[i]));continue;}
		if(v[l[i]].size()>v[r[i]].size())swap(l[i],r[i]);
		for(int j=0,k=0;j<v[l[i]].size();++j)
		{
			for(;k<v[r[i]].size()&&v[l[i]][j].first+v[r[i]][k].second-d[i]*2>x;++k);
			if(k==v[r[i]].size())break;
			V.push_back(make_pair(v[l[i]][j].second,v[r[i]][k].first));
			V.push_back(make_pair(v[r[i]][k].first,v[l[i]][j].second));
		}
		sort(V.begin(),V.end());
		for(int j=0;j<V.size();++j)if(!j||V[j].second<V[j-1].second)v[i].push_back(V[j]);
		if(!v[i].size())return false;
	}
	return true;
}
int main()
{
	int i,x;ll mid,ans;
	for(n=read(),i=2;i<=n;++i)x=read(),(l[x]?r[x]:l[x])=i,d[i]=d[x]+read();
	for(ll l=0,r=1LL<<34;l<=r;)if(check(mid=l+r>>1))ans=mid,r=mid-1;else l=mid+1;
	printf("%lld",ans);
}

Submission Info

Judge Result