Language: C++

#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
using namespace std;
typedef long long s64;

const int ONE = 1000005;
const int INF = 2147483640;

int get()
{
		int res = 1, Q = 1; char c;
		while( (c = getchar()) < 48 || c > 57)
			if(c == '-') Q = -1;
		if(Q) res = c - 48;
		while( (c = getchar()) >= 48 && c <= 57)
			res = res * 10 + c - 48;
		return res * Q;
}

struct power
{
		s64 a, b;
		bool operator <(power A) const
		{
			if(A.a != a) return a < A.a;
			return b < A.b;
		}
};
vector <power> A[ONE], R;

int n;
int x, y;
s64 l, r, K;
int next[ONE], first[ONE], go[ONE], w[ONE], tot;
int size[ONE], times[ONE], fat[ONE];

void Add(int u, int v, int z)
{
		next[++tot] = first[u], first[u] = tot, go[tot] = v, w[tot] = z;
		next[++tot] = first[v], first[v] = tot, go[tot] = u, w[tot] = z;
}

int dist[ONE];
int len_x, len_y;
s64 a1, b1, a2, b2;

int Find()
{
		if(len_y == 0) return len_y;
		int l = 0, r = len_y - 1;
		while(l < r - 1)
		{
			int mid = l + r >> 1;
			a2 = A[y][mid].a, b2 = A[y][mid].b;
			if(b1 + a2 + dist[x] + dist[y] <= K) l = mid;
			else r = mid;
		}
		a2 = A[y][r].a, b2 = A[y][r].b; if(b1 + a2 + dist[x] + dist[y] <= K) return r;
		a2 = A[y][l].a, b2 = A[y][l].b; if(b1 + a2 + dist[x] + dist[y] <= K) return l;
		return len_y;
}

void Update(int u)
{
		x = 0, y = 0;
		for(int e = first[u]; e; e = next[e])
			if(go[e] != fat[u])
				if(!x) x = go[e]; else y = go[e];

		if(size[x] > size[y]) swap(x, y);
	//	cout<<"FKFKFKFK===="<<u<<" "<<x<<" "<<y<<endl;

		len_x = A[x].size(), len_y = A[y].size();

		R.clear();
		for(int i = 0; i < len_x; i++)
		{
			a1 = A[x][i].a, b1 = A[x][i].b;
			int id = Find();
			if(id >= len_y) continue;
		//	cout<<y<<" "<<len_y<<" "<<id<<endl;
		//	cout<<u<<"======"<<dist[x]<<","<<b2+dist[y]<<endl;
			R.push_back((power){a1 + dist[x], b2 + dist[y]});
			R.push_back((power){b2 + dist[y], a1 + dist[x]});
		}
	//	cout<<"FKFKFKFK===="<<u<<" "<<x<<" "<<y<<endl;


		sort(R.begin(), R.end());
		int len = R.size(), maxx = INF;
/*		cout<<u<<":"<<endl;
		for(int i = 0; i < len; i++)
			cout<<R[i].a<<" "<<R[i].b<<endl;
*/
		for(int i = 0; i < len; i++)
			if(R[i].b < maxx)
			{
				if(i != 0 && R[i - 1].a == R[i].a) continue;
				A[u].push_back((power){R[i].a, R[i].b}), maxx = R[i].b;
			//	cout<<R[i].a<<" "<<R[i].b<<endl;
			}
}

void Dfs(int u, int father)
{
		size[u] = 1, times[u] = 0;
		int pd = 1;
		for(int e = first[u]; e; e = next[e])
		{
			int v = go[e];
			if(v == father) continue;
			pd = 0, fat[v] = u, dist[v] = w[e];
			Dfs(v, u);
			size[u] += size[v], times[u]++;
			if(times[u] == 2) Update(u);
		}
		if(pd) A[u].push_back((power){0, 0});
}

int Check()
{
		for(int i = 1; i <= n; i++)
			A[i].clear();
		Dfs(1, 0);

	/*	for(int i = 1; i <= n; i++)
		{
			cout<<i<<":    "<<A[i].size()<<endl;
			for(int j = 0; j < A[i].size(); j++)
				cout<<A[i][j].a<<" "<<A[i][j].b<<endl;
			cout<<endl;
		}
*/
		return A[1].size() > 0;
}

int main()
{
		//freopen(".in","r",stdin);
		//freopen(".out","w",stdout);
		n = get();
		for(int i = 2; i <= n; i++)
		{
			x = get(), y = get();
			Add(i, x, y), r += y;
		}


		while(l < r - 1)
		{
			K = l + r >> 1;
			if(Check()) r = K;
			else l = K;
		}

		K = l;
		if(Check()) printf("%d", l);
		else printf("%d", r);
}

Compiler output:
a.cc: In function 'void Add(int, int, int)':
a.cc:45:17: error: reference to 'next' is ambiguous
   45 |                 next[++tot] = first[u], first[u] = tot, go[tot] = v, w[tot] = z;
      |                 ^~~~
In file included from /usr/include/c++/14/string:47,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:40:5: note:                 'int next [1000005]'
   40 | int next[ONE], first[ONE], go[ONE], w[ONE], tot;
      |     ^~~~
a.cc:46:17: error: reference to 'next' is ambiguous
   46 |                 next[++tot] = first[v], first[v] = tot, go[tot] = u, w[tot] = z;
      |                 ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:40:5: note:                 'int next [1000005]'
   40 | int next[ONE], first[ONE], go[ONE], w[ONE], tot;
      |     ^~~~
a.cc: In function 'void Update(int)':
a.cc:72:46: error: reference to 'next' is ambiguous
   72 |                 for(int e = first[u]; e; e = next[e])
      |                                              ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:40:5: note:                 'int next [1000005]'
   40 | int next[ONE], first[ONE], go[ONE], w[ONE], tot;
      |     ^~~~
a.cc:76:20: error: reference to 'size' is ambiguous
   76 |                 if(size[x] > size[y]) swap(x, y);
      |                    ^~~~
In file included from /usr/include/c++/14/string:53:
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:41:5: note:                 'int size [1000005]'
   41 | int size[ONE], times[ONE], fat[ONE];
      |     ^~~~
a.cc:76:30: error: reference to 'size' is ambiguous
   76 |                 if(size[x] > size[y]) swap(x, y);
      |                              ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:41:5: note:                 'int size [1000005]'
   41 | int size[ONE], times[ONE], fat[ONE];
      |     ^~~~
a.cc: In function 'void Dfs(int, int)':
a.cc:112:17: error: reference to 'size' is ambiguous
  112 |                 size[u] = 1, times[u] = 0;
      |                 ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:41:5: note:                 'int size [1000005]'
   41 | int size[ONE], times[ONE], fat[ONE];
      |     ^~~~
a.cc:114:46: error: reference to 'next' is ambiguous
  114 |                 for(int e = first[u]; e; e = next[e])
      |                                              ^~~~
/usr/include/c++/14/bits/stl_iterator_base_funcs.h:232:5: note: candidates are: 'template<class _InputIterator> constexpr _InputIterator std::next(_InputIterator, typename iterator_traits<_Iter>::difference_type)'
  232 |     next(_InputIterator __x, typename
      |     ^~~~
a.cc:40:5: note:                 'int next [1000005]'
   40 | int next[ONE], first[ONE], go[ONE], w[ONE], tot;
      |     ^~~~
a.cc:120:25: error: reference to 'size' is ambiguous
  120 |                         size[u] += size[v], times[u]++;
      |                         ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:41:5: note:                 'int size [1000005]'
   41 | int size[ONE], times[ONE], fat[ONE];
      |     ^~~~
a.cc:120:36: error: reference to 'size' is ambiguous
  120 |                         size[u] += size[v], times[u]++;
      |                                    ^~~~
/usr/include/c++/14/bits/range_access.h:272:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  272 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/14/bits/range_access.h:262:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  262 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
a.cc:41:5: note:                 'int size [1000005]'
   41 | int size[ONE], times[ONE], fat[ONE];
      |     ^~~~