Submission #1693171

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define X first
#define Y second

const int maxn=131072+233;

int n,fa[maxn],lc[maxn],rc[maxn],w[maxn];
LL mid;
vector<pair<LL,LL> > S[maxn],t1,t2;

void dfs(int u)
{
	if (!lc[u])
	{
		S[u].push_back(make_pair(w[u],w[u]));
		return;
	}
	dfs(lc[u]); dfs(rc[u]);

	int i,j=-1,m=S[rc[u]].size()-1;
	LL last;
	t1.clear(); t2.clear();
	for (i=0;i<(int)S[lc[u]].size();i++)
	{
		bool flag=0;
		while (j<m&&S[lc[u]][i].Y+S[rc[u]][j+1].X<=mid) j++,flag=1;
		if (flag)
		{
			t1.push_back(make_pair(S[lc[u]][i].X+w[u],S[rc[u]][j].Y+w[u]));
			t2.push_back(make_pair(S[rc[u]][j].Y+w[u],S[lc[u]][i].X+w[u]));
		}
	}
	for (last=1e18,m=t1.size(),i=0,j=m-1;i<m||j>=0;)
	{
		bool flag=i==m?0:j==-1?1:t1[i]<t2[j];
		pair<LL,LL> pr=flag?t1[i++]:t2[j--];
		if (last>pr.Y) last=pr.Y,S[u].push_back(pr);
	}
}

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i;
	LL L=0,R=0;
	scanf("%d",&n);
	for (i=2;i<=n;i++)
	{
		scanf("%d%d",&fa[i],&w[i]);
		if (lc[fa[i]]) rc[fa[i]]=i;
		else lc[fa[i]]=i;
		R+=w[i];
	}
	while (L<=R)
	{
		mid=(L+R)>>1;
		for (i=1;i<=n;i++) S[i].clear();
		dfs(1);
		S[1].size()?R=mid-1:L=mid+1;
	}
	printf("%lld\n",L);
}

Submission Info

Compile Error

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

Judge Result