Submission #1690828

---

Source Code Expand

#include <cstdio>

const int N=131100;
int l[N],r[N],lef[N],rig[N],v[N],cnt,tot;
long long Mid;

struct P{
	long long x,y;
	P(const int xx=0,const int yy=0):x(xx),y(yy){}
}a[N],b[N];

void solve(int l1,int r1,int l2,int r2,long long val,int v1,int v2){
	for (int i=l1,j=l2;i<=r1;i++){
		for (;j<=r2 && a[i].y+a[j].x<=val;j++);
		if (j>l2) b[++tot]=P(a[i].x+v1,a[j-1].y+v2);
	}
}

int merge(int mid,int r,int l){
	int t=l-1;
	for (int i=1,j=mid+1;i<=mid || j<=r;){
		P po;
		if (i<=mid && (j>r || b[i].x<b[j].x)) po=b[i++];
			else po=b[j++];
		if (t<l) a[++t]=po;
		else if (a[t].x<po.x && a[t].y>po.y) a[++t]=po;
		else if (a[t].x==po.x && a[t].y>po.y) a[t].y=po.y;
	}
	return t;
}

bool dfs(int x){
	int s1=l[x],s2=r[x];
	if (!s1){
		lef[x]=rig[x]=++cnt;
		a[cnt].x=a[cnt].y=0;
		return 1;
	}
	if (!dfs(s1) || !dfs(s2)) return 0;
	long long val=Mid-v[s1]-v[s2];
	tot=0;lef[x]=lef[s1];
	solve(lef[s1],rig[s1],lef[s2],rig[s2],val,v[s1],v[s2]);
	int m=tot;
	solve(lef[s2],rig[s2],lef[s1],rig[s1],val,v[s2],v[s1]);
	rig[x]=merge(m,tot,lef[x]);
	return lef[x]<=rig[x];
}

int main(){
	int n;
	scanf("%d\n",&n);
	long long L=0,R=0,ans=0;
	for (int i=2;i<=n;i++){
		int fa;
		scanf("%d%d",&fa,&v[i]);
		if (!l[fa]) l[fa]=i;
			else r[fa]=i;
		R+=v[i];
	}
	for (;L<=R;){
		Mid=(L+R)>>1;
		cnt=0;
		if (dfs(1)) ans=Mid,R=Mid-1;
			else L=Mid+1;
	}
	printf("%lld\n",ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:51:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n",&n);
                  ^
./Main.cpp:55:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&fa,&v[i]);
                          ^

Judge Result