Submission #1613562

---

Source Code Expand

#include <bits/stdc++.h>
#define N 100050

#define x first
#define y second

using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
pii f[N],tmp1[N],tmp2[N];
int ch[N][2],fa[N],v[N],tp[N],vis[N],le[N],ri[N],mid[N],n,m;
LL lim;
bool flag;

void link(int a,int b) {ch[a][0] ? ch[a][1] = b : ch[a][0] = b;}
inline int rd() {int r;scanf("%d",&r);return r;}

void solve(int u,int l,int r) {
	if (!flag) return ;
	if (!ch[u][0] && !ch[u][1]) {
		f[l] = pii(v[u], v[u]);
		tp[u] = l;
		return ;
	}
	int L = ch[u][0], R = ch[u][1];
	solve(L, l, mid[u]);
	solve(R, mid[u]+1, r);

	int T = tp[R], q1 = 0, q2 = 0;
	for (int i=tp[L];i>=l;i--) {
		while (T>=mid[u]+1 && f[i].y+f[T].x > lim) T--;
		if (T>=mid[u]+1 && f[i].y + f[T].x <= lim)
			tmp1[++q1] = pii(f[i].x, f[T].y);
	}

	T = tp[L];
	for (int i=tp[R];i>=mid[u]+1;i--) {
		while (T>=l && f[i].y+f[T].x > lim) T--;
		if (T>=l && f[i].y+f[T].x <= lim)
			tmp2[++q2] = pii(f[i].x, f[T].y);
	}

	if (!q1 && !q2) {flag = 0; return ;}
	tp[u] = l-1;
	while (q1 || q2) {
		pii cur;
		if (q1 && q2)
			cur = tmp1[q1].x < tmp2[q2].x ? tmp1[q1--] : tmp2[q2--];
		else
			cur = !q1 ? tmp2[q2--] : tmp1[q1--];
		if (tp[u] >= l && cur.y >= f[ tp[u] ].y) continue;
		f[ ++tp[u] ] = cur;
	}
	for (int _=l;_<=tp[u];_++) f[_].x += v[u], f[_].y += v[u];

}

void dfs(int u) {
	if (!ch[u][0] && !ch[u][1]) {
		le[u] = ri[u] = ++m;
		return ;
	}
	dfs(ch[u][0]); dfs(ch[u][1]);
	le[u] = le[ ch[u][0] ];
	ri[u] = ri[ ch[u][1] ];
	mid[u] = ri[ ch[u][0] ];
}

bool go(LL x) {
	lim = x, flag = 1;
	solve(1,1,m);
	return flag;
}

int main() {
	n = rd();
	for (int _=2;_<=n;_++) {
		fa[_] = rd(), v[_] = rd();
		link(fa[_], _);
		if (!vis[ fa[_] ]) vis[ fa[_] ] = 1;
	}

	dfs(1);
	LL l = 1, r = 100000000000LL;
	while (l < r) {
		LL mi = (l + r) >> 1;
		if (go(mi)) r = mi; else l = mi + 1;
	}
	cout << l << endl;
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int rd()’:
./Main.cpp:16:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 inline int rd() {int r;scanf("%d",&r);return r;}
                                      ^

Judge Result