Submission #1627846

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define MAXN 200010
using namespace std;

int n;
int pre[MAXN],ch[MAXN][2];
int size[MAXN],sf[MAXN];
LL v[MAXN],lim;
pair<LL,LL> *f[MAXN];

void dfs(int x){
	if(ch[x][0]){
		dfs(ch[x][0]);
		dfs(ch[x][1]);
		if(size[ch[x][0]]>size[ch[x][1]]) swap(ch[x][0],ch[x][1]);
		size[x]=size[ch[x][0]]<<1;
	}else{
		size[x]=1;
	}
	f[x]=new pair<LL,LL>[size[x]+1];
}

int join(pair<LL,LL> *fs,pair<LL,LL> *f0,pair<LL,LL> *f1,int sf0,int sf1){
	int now0=1,now1=1;
	int sfs=0;
	while(now0<=sf0 || now1<=sf1){
		if(now1>sf1){
			if(!sfs || fs[sfs].second>f0[now0].second)
				fs[++sfs]=f0[now0];
			now0++;
		}else if(now0>sf0){
			if(!sfs || fs[sfs].second>f1[now1].second)
				fs[++sfs]=f1[now1];
			now1++;
		}else if(f0[now0].first<f1[now1].first){
			if(!sfs || fs[sfs].second>f0[now0].second)
				fs[++sfs]=f0[now0];
			now0++;
		}else{
			if(!sfs || fs[sfs].second>f1[now1].second)
				fs[++sfs]=f1[now1];
			now1++;
		}
	}
	return sfs;
}

bool gao(int x){
	if(!ch[x][0]){
		sf[x]=1;
		f[x][1]=make_pair(0,0);
		return 1;
	}
	int c0=ch[x][0],c1=ch[x][1];
	if(!gao(c0)) return 0; 
	if(!gao(c1)) return 0;
	LL delta=v[c0]+v[c1];
	static pair<LL,LL> f0[MAXN],f1[MAXN];
	int sf0=0,sf1=0;
	int now=sf[c1];
	for(int i=1;i<=sf[c0];i++){
		while(now && f[c0][i].second+f[c1][now].first+delta>lim) now--;
		if(!now) break;
		f0[++sf0]=make_pair(f[c0][i].first+v[c0],f[c1][now].second+v[c1]);
	}
	now=1;
	for(int i=1;i<=sf[c0];i++){
		while(now<=sf[c1] && f[c0][i].first+f[c1][now].second+delta>lim) now++;
		if(now>sf[c1]) break;
		f1[++sf1]=make_pair(f[c1][now].first+v[c1],f[c0][i].second+v[c0]);
	}
	sf[x]=join(f[x],f0,f1,sf0,sf1);
	return sf[x];
}

bool check(LL _lim){
	lim=_lim;
	return gao(1);
}

int main(){
#ifdef DEBUG
	freopen("E.in","r",stdin);
#endif
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		scanf("%d%lld",pre+i,v+i);
		if(!ch[pre[i]][0]) ch[pre[i]][0]=i;
		else ch[pre[i]][1]=i;
	}
	dfs(1);
	LL l=0,r=131072LL*131072LL;
	while(l<r){
		LL mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	printf("%lld\n",l);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:88:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:90:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%lld",pre+i,v+i);
                            ^

Judge Result