Submission #1692067

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>

using namespace std;

const int MAXN = 200000 + 100;
const long long INF = 0x1f1f1f1f1f1f1f1fll;

typedef pair<int, int> pii;
typedef vector<pii> vpii;

int n;
vector<int> son[MAXN], wei[MAXN];
vector<pair<int, int> > list[MAXN];
long long f[MAXN];

void merge(const vpii &a, const vpii &b, vpii &c)
{
	// int l = 0, r = 0;
	// while(l < a.size() && r < b.size())
	// 	if(a[l] < b[r])
	// 		c.push_back(a[l]), l++;
	// 	else
	// 		c.push_back(b[r]), r++;
	// while(l < a.size())
	// 	c.push_back(a[l]), l++;
	// while(r < b.size())
	// 	c.push_back(b[r]), r++;
	int l = a.size() - 1, r = b.size() - 1;
	while(~l && ~r)
		if(a[l] < b[r])
			c.push_back(a[l]), l--;
		else
			c.push_back(b[r]), r--;
	while(~l)
		c.push_back(a[l]), l--;
	while(~r)
		c.push_back(b[r]), r--;
}

void arange(vpii &a)
{
	if(!a.size()) return ;
	int p = 0;
	a[p] = a[0], p++;
	for(int i = 1; i < a.size(); i++)
		if(!(a[i - 1].first <= a[i].first && a[i - 1].second <= a[i].second))
			a[p] = a[i], p++;
	a.resize(p);
}

void print(vpii &a)
{
	for(int i = 0; i < a.size(); i++)
		cout << a[i].first << ' ' << a[i].second << " / ";
	cout << endl;
}

bool dfs(int x, int fa, long long k)
{
	// cout << k << " : " << x << endl;
	if(son[x].size() == 0)
	{
		list[x].push_back(make_pair(0, 0));
		return true;
	}
	int s0 = son[x][0], s1 = son[x][1], w0 = wei[x][0], w1 = wei[x][1];
	if(!dfs(s0, x, k) || !dfs(s1, x, k)) return false;
	// for(int i = 0; i < 2; i++)
	// 	for(int j = 0; j < list[son[x][i]].size(); j++)
	// 		list[son[x][i]][j] = make_pair(list[son[x][i]][j].first + wei[x][i], list[son[x][i]][j].second + wei[x][i]);
	if(list[s0].size() > list[s1].size()) swap(s0, s1), swap(w0, w1);
	static vector<pair<int, int> > arr0, arr1;
	arr0.clear(), arr1.clear();
	int r = list[s1].size() - 1, l = 0;
	for(int i = list[s0].size() - 1; i >= 0; i--)
	{
		while(r >= 0 && list[s0][i].second + list[s1][r].first + w0 + w1 > k) r--;
		while(l < list[s1].size() && list[s0][i].second + list[s1][l].second + w0 + w1 > k) l++;
		if(r >= 0 && l < list[s1].size())
			arr0.push_back(make_pair(list[s0][i].first + w0, min(list[s1][r].second, list[s1][l].first) + w1));
		else if(r >= 0)
			arr0.push_back(make_pair(list[s0][i].first + w0, list[s1][r].second + w1));
		else if(l < list[s1].size())
			arr0.push_back(make_pair(list[s0][i].first + w0, list[s1][l].first + w1));
	}
	r = list[s1].size() - 1, l = 0;
	for(int i = 0; i < list[s0].size(); i++)
	{
		while(r >= 0 && list[s0][i].first + list[s1][r].first + w0 + w1 > k) r--;
		while(l < list[s1].size() && list[s0][i].first + list[s1][l].second + w0 + w1 > k) l++;
		if(r >= 0 && l < list[s1].size())
			arr1.push_back(make_pair(list[s0][i].second + w0, min(list[s1][r].second, list[s1][l].first) + w1));
		else if(r >= 0)
			arr1.push_back(make_pair(list[s0][i].second + w0, list[s1][r].second + w1));
		else if(l < list[s1].size())
			arr1.push_back(make_pair(list[s0][i].second + w0, list[s1][l].first + w1));
	}
	// cout << x << ' ' << arr0.size() << ' ' << arr1.size() << endl;
	// for(int i = 0; i < arr0.size(); i++)
	// 	cout << arr0[i].first << ' ' << arr0[i].second << endl;
	// for(int i = 0; i < arr1.size(); i++)
	// 	cout << arr1[i].first << ' ' << arr1[i].second << endl;
	if(arr0.size() + arr1.size() == 0)
		return false;
	// reverse(arr0.begin(), arr0.end());
	// reverse(arr1.begin(), arr1.end());

	// cout << x << endl, print(arr0), , print(arr0);
	// cout << endl;
	// arange(arr0);
	// arange(arr1);
	merge(arr0, arr1, list[x]);
	// arange(list[x]);

	// cout << x << " : ", print(list[x]);

	return true;
}

bool calc(long long k)
{
	for(int i = 1; i <= n; i++)
		list[i].clear();
	return dfs(1, 0, k);
}

void solve()
{
	long long l = 0, r = 10000000000ll, ans = 0;
	while(l < r)
	{
		long long mid = (l + r) / 2;
		if(calc(mid))
			r = mid, ans = mid;
		else
			l = mid + 1;
	}
	cout << ans << endl;
}

int main()
{
	ios::sync_with_stdio(false);
	// freopen("travel.in", "r", stdin);
	// freopen("travel.out", "w", stdout);

	cin >> n;
	for(int i = 2; i <= n; i++)
	{
		int x, z;
		cin >> x >> z;
		son[x].push_back(i), wei[x].push_back(z);
	}

	solve();

	return 0;
}

Submission Info

Judge Result