Submission #7964497

---

Source Code Expand

#include<bits/stdc++.h>
#define pr std::pair<ll,ll>
#define fir first
#define sec second
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
ll mid;
std::vector<pr>f[131113];
int ls[131113],lw[131113],rs[131113],rw[131113];
void Merge(int A,int B,std::vector<pr>&F){
	int i=0;
	for(pr _:f[A]){
		ll a=_.fir,b=_.sec;
		while(i<f[B].size()-1&&b+f[B][i+1].fir<=mid)++i;
		if(i<f[B].size()&&b+f[B][i].fir<=mid){
			ll d=f[B][i].sec;
			F.emplace_back(a,d);
			F.emplace_back(d,a);
		}
	}
}
void dfs(int x){
	f[x].clear();
	if(!ls[x]){f[x].emplace_back(0,0);return;}
	dfs(ls[x]),dfs(rs[x]);
	if(f[ls[x]].size()>f[rs[x]].size())std::swap(ls[x],rs[x]),std::swap(lw[x],rw[x]);
	for(pr&i:f[ls[x]])i.fir+=lw[x],i.sec+=lw[x];
	for(pr&i:f[rs[x]])i.fir+=rw[x],i.sec+=rw[x];
	Merge(ls[x],rs[x],f[x]);
	std::sort(f[x].begin(),f[x].end());
	pr lst(-1,9e18);
	for(pr&i:f[x])
		if(i.sec>=lst.sec)i.fir=9e18;
		else lst=i;
	std::sort(f[x].begin(),f[x].end());
	while(!f[x].empty()&&f[x].back().fir==9e18)f[x].pop_back();
}
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi();
	for(int i=2;i<=n;++i){
		int fa=gi(),w=gi();
		if(ls[fa])rs[fa]=i,rw[fa]=w;
		else ls[fa]=i,lw[fa]=w;
	}
	ll l=0,r=n*131072ll;
	while(l<r){
		mid=(l+r)>>1;
		dfs(1);
		if(!f[1].empty())r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
	return 0;
}

Submission Info

Judge Result