Submission #1693145

---

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],tmp;

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;
	int m=(int)S[rc[u]].size()-1;
	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)
			S[u].push_back(make_pair(S[lc[u]][i].X+w[u],S[rc[u]][j].Y+w[u]));
	}

	m=(int)S[u].size();
	for (i=0;i<m;i++)
		S[u].push_back(make_pair(S[u][i].Y,S[u][i].X));
	sort(S[u].begin(),S[u].end());
	LL last=1e15;
	tmp.clear();
	for (i=0;i<(int)S[u].size();i++)
		if (last>S[u][i].Y) last=S[u][i].Y,tmp.push_back(S[u][i]);
	S[u].clear();
	for (i=0;i<(int)tmp.size();i++)
		S[u].push_back(tmp[i]);

//	printf("S[%d]:\n",u);
//	for (i=0;i<(int)S[u].size();i++)
//		printf("%lld %lld\n",S[u][i].X,S[u][i].Y);
//	puts("");
}

bool pass()
{
//	printf("<<<pass %lld>>>\n",mid);
	int i;
	for (i=1;i<=n;i++)
		S[i].clear();
	dfs(1);
//	puts(""); puts(""); puts(""); puts(""); puts("");
	return S[1].size();
}

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;
		if (pass()) R=mid-1;
		else L=mid+1;
	}
	printf("%lld\n",L);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:69:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:72: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