Submission #1610896

---

Source Code Expand

#ifdef DEBUG
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <cassert>
#include <sstream>
#include <fstream>
#include <functional>
#include <set>
#include <bitset>
#include <string>
#include <utility>
#include <queue>
#include <deque>
#include <vector>
#include <map>
#else
#include <bits/stdc++.h>
#endif

#ifdef DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif

#define rep(i, n) for (int i = 0, i##_end_ = (n); i < i##_end_; ++i)
#define per(i, n) for (int i = (n) - 1; i >= 0; --i)
#define forn(i, l, r) for (int i = (l), i##_end_ = (r); i <= i##_end_; ++i)
#define nrof(i, r, l) for (int i = (r), i##_end_ = (l); i >= i##_end_; --i)
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) (x).begin(), (x).end()

using namespace std;

typedef vector<int> vi;

typedef pair<int, int> pii;

typedef long long LL;

template<typename T> inline bool chkmax(T &x, const T &y) {
	return x < y ? x = y, 1 : 0;
}

template<typename T> inline bool chkmin(T &x, const T &y) {
	return x > y ? x = y, 1 : 0;
}

#ifdef DEBUG
char *input_file, *output_file;
#endif

struct IO {
	static const int maxn = (1 << 25) + 10;

	char a[maxn], *s, b[maxn], *t;

	void INPUT() {
		s = a;
		t = b;
		#ifdef DEBUG
		FILE *f = fopen(input_file, "r");
		a[fread(a, 1, sizeof a, f)] = 0;
		#else
		a[fread(a, 1, sizeof a, stdin)] = 0;
		#endif
	}

	void OUTPUT() {
#ifdef DEBUG
		FILE *f = fopen(output_file, "w");
		fwrite(b, 1, t - b, f);
#else
		fwrite(b, 1, t - b, stdout);
#endif
	}

	operator int() {
		int x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator LL() {
		LL x = 0;
		while(*s != '-' && (*s < '0' || *s > '9')) {
			++s;
		}
		bool f = 0;
		if(*s == '-') {
			f = 1;
			++s;
		}
		while(*s >= '0' && *s <= '9') {
			(x *= 10) += *s - '0';
			++s;
		}
		if(f) {
			x = -x;
		}
		return x;
	}

	operator char() {
		while(*s <= 32) {
			++s;
		}
		char ret = *s;
		++s;
		return ret;
	}

	inline void out(int x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(int x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			int y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(LL x) {
		if(!x) {
			*t++ = '0';
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		return;
	}

	inline void out(LL x, char C) {
		if(!x) {
			*t++ = '0';
			*t++ = C;
			return;
		}
		if(x < 0) {
			*t++ = '-';
			x = -x;
		}
		static char c[20], *i;
		i = c;
		while(x) {
			LL y = x / 10;
			*i++ = x - y * 10 + '0';
			x = y;
		}
		while(i != c) {
			*t++ = *--i;
		}
		*t++ = C;
		return;
	}

	inline void out(char c) {
		*t++ = c;
		return;
	}

	inline void out(char *s) {
		while(*s >= ' ') {
			*t++ = *s++;
		}
		return;
	}
}io;

void Main();

int main(int argc, char *argv[]) {
#ifdef DEBUG
	input_file = argv[1];
	output_file = argv[2];
#endif
	io.INPUT();
	Main();
	io.OUTPUT();
	return 0;
}

//---------------------------------------------------------------------------------------head---------------------------------------------------------------------------------------

const LL oo = 1ll << 62;

const int maxn = 132000;

struct edge {
	int to, next;
	LL w;

	edge() {}
	edge(int to, int next, LL w): to(to), next(next), w(w) {}
}e[maxn];

int n, m;
int head[maxn];
LL bound;
vector<pair<LL, LL> > vec, s[maxn], tmp;

void add_edge(int u, int v, LL w) {
	e[m] = edge(v, head[u], w);
	head[u] = m++;
	return;
}

void B(int u, LL delta) {
	vec.clear();
	for(auto x: s[u]) {
		LL a = x.X, b = x.Y;
		if(b + delta <= bound) {
			vec.pb(mp(a, b + delta));
		}
	}
	s[u].clear();
	return;
}

void dfs(int u = 1) {
	if(!~head[u]) {
		s[u] = {mp(0, 0)};
		return;
	}
	s[u].clear();
	int son, chd = 0, mx = 0;
	LL delta = 0, wc, ws;
	for (int i = head[u]; ~i; i = e[i].next) {
		int &v = e[i].to;
		dfs(v);
		if(!SZ(s[v])) {
			return;
		}
		delta += e[i].w;
		chd += v;
		if(chkmax(mx, SZ(s[v]))) {
			son = v;
			ws = e[i].w;
		}
	}
	chd -= son;
	wc = delta - ws;
	B(chd, delta);
	LL mn = oo;
	tmp.clear();
	for(auto &ivec: vec) {
		LL &a = ivec.X, &b = ivec.Y;
		if(!chkmin(mn, b)) {
			continue;
		}
		int lb = 0, rb = SZ(s[son]) - 1;
		while(lb <= rb) {
			int mid = lb + rb >> 1;
			if(s[son][mid].X + b > bound) {
				rb = mid - 1;
			}
			else {
				lb = mid + 1;
			}
		}
		int i = rb;
		if(i >= 0) {
			tmp.pb(mp(a + wc, s[son][i].Y + ws));
		}
	}
	s[son].clear();
	for (int sz = SZ(tmp), i = 0, j = 0; i < sz || j < sz; ) {
		if(i == sz || j < sz && tmp[sz - j + 1] < tmp[i]) {
			s[u].pb(tmp[sz - ++j]);
		}
		else {
			s[u].pb(tmp[i++]);
		}
	}
	int sz = 0;
	mn = oo;
	rep(i, SZ(s[u])) {
		if(chkmin(mn, s[u][i].Y)) {
			s[u][sz++] = s[u][i];
		}
	}
	s[u].resize(sz);
	return;
}

bool check(LL mid) {
	bound = mid;
	dfs();
	return SZ(s[1]);
}

void Main() {
	n = io;
	LL lb = 0, rb = 0;
	memset(head, -1, sizeof(head[0]) * (n + 1));
	forn(i, 2, n) {
		int u = io;
		LL w = io;
		rb += w;
		add_edge(u, i, w);
	}
	while(lb <= rb) {
		LL mid = lb + rb >> 1;
		if(check(mid)) {
			rb = mid - 1;
		}
		else {
			lb = mid + 1;
		}
	}
	io.out(lb, '\n');
	return;
}

Submission Info

Judge Result