Language: C++

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 8;
const int INF = 1e9 + 7;
struct edge
{
	int u, v, w, nt;
}eg[N << 2];
int lt[N], sum;
int n;
int gas[N];
int vis[N];
int a[N], b[N];
int tot, root;
int size[N], sizeMax[N];
struct node
{
	int x, len;
};
vector <node> f, g;
int p[N], num;
int ans, flag;
void add(int u, int v, int w)
{
	eg[++sum] = (edge){u, v, w, lt[u]}; lt[u] = sum;
}
struct Sement_Tree
{
	int tag[N << 2];
	void build(int l, int r, int rt)
	{
		tag[rt] = -1;
		if (l == r)
		{
			return;
		}
		int m = l + r >> 1;
		build(l, m, rt << 1);
		build(m + 1, r, rt << 1 | 1);
		tag[rt] = tag[rt << 1] + tag[rt << 1 | 1];
	}
	void update(int x, int val, int l, int r, int rt)
	{
		if (l == r)
		{
			tag[rt] = val;
			return;
		}
		int m = l + r >> 1;
		if (x <= m) update(x, val, l, m, rt << 1);
		else update(x, val, m + 1, r, rt << 1 | 1);
		tag[rt] = tag[rt << 1] + tag[rt << 1 | 1];
	}
	int query(int L, int R, int l, int r, int rt)
	{
		if (L <= l && r <= R)
		{
			return tag[rt];
		}
		int m = l + r >> 1;
		int res = -1;
		if (L <= m) res = max(res, query(L, R, l, m, rt << 1));
		if (m <  R) res = max(res, query(L, R, m + 1, r, rt << 1 | 1));
		return res;
	}
}T;
void init()
{
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> gas[i];
	for (int i = 1; i <  n; ++i)
	{
		int u, v, w; 
		cin >> u >> v >> w;
		add(u, v, w);
		add(v, u, w);
	}	
}
void getRoot(int u, int fa = 0)
{
	size[u] = 1;
	for (int i = lt[u]; i; i = eg[i].nt)
	{
		int v = eg[i].v;
		if (v == fa || vis[v]) continue;
		getRoot(v, u);
		size[u] += size[v];
		sizeMax[u] = max(sizeMax[u], size[v]);
	}
	sizeMax[u] = max(sizeMax[u], tot - size[u]);
	if (sizeMax[u] < sizeMax[root]) root = u;
}
void getToDp(int u, int fa = 0, int need = 0, int deep = 0)
{
	b[u] = max(b[fa], need);
	g.push_back((node){b[u], deep});
	for (int i = lt[u]; i; i = eg[i].nt)
	{
		int v = eg[i].v;
		if (v == fa || vis[v]) continue;
		getToDp(v, u, need + eg[i].w - gas[u], deep + 1);
	}
}
void getFromDp(int u, int fa = 0, int delta = 0, int deep = 0, int ok = 1)
{
	if (ok) a[u] = -delta; else a[u] = -1;
	f.push_back((node){a[u], deep});
	for (int i = lt[u]; i; i = eg[i].nt)
	{
		int v = eg[i].v;
		if (v == fa || vis[v]) continue;
		getFromDp(v, u, delta + eg[i].w - gas[v], deep + 1, gas[v] >= eg[i].w + max(0, delta));
	}
}
vector <edge> vec;

void work(int u)
{
	f.clear();
	getFromDp(u);
	num = 0;
	for (auto w : f) p[++num] = w.x;
	sort(p + 1, p + num + 1);
	num = unique(p + 1, p + num + 1)- p - 1;
	vec.clear();
	for (int i = lt[u]; i; i = eg[i].nt) if (!vis[eg[i].v]) vec.push_back(eg[i]);
	b[u] = 0;
	for (int cas = 1; cas <= 2; ++cas)
	{
		T.build(1, num, 1);
		T.update(1, 0, 1, num, 1);
		if (cas == 2) reverse(vec.begin(), vec.end());
		for (auto q : vec)
		{
			f.clear(); g.clear();
			getToDp(q.v, u, q.w - gas[u], 1);
			getFromDp(q.v, u, q.w - gas[q.v], 1, gas[q.v] >= q.w);
			for (auto w : g) 
			{
				int x = lower_bound(p + 1, p + num + 1, w.x) - p;
				if (x != num + 1)
				{
					int mx = T.query(x, num, 1, num, 1);
					if (mx != -1) ans = max(ans, mx + w.len);
				}
			}
			for (auto w : f)
			{
				int x = lower_bound(p + 1, p + num + 1, w.x) - p;
				T.update(x, w.len, 1, num, 1);
			}
		}
	}
	int x = lower_bound(p + 1, p + num + 1, 0) - p;
	int mx = T.query(x, num, 1, num, 1);
	if (mx != -1) ans = max(ans, mx);

	vis[u] = 1;
	for (int i = lt[u]; i; i = eg[i].nt)
	{
		int v = eg[i].v;
		if (vis[v]) continue;
		tot = size[v]; root = 0;
		getRoot(v);
		work(v);
	}
}
void solve()
{
	tot = n; sizeMax[root = 0] = n;
	getRoot(1);
	ans = 0;
	work(root);
//	getToDp(2);
//	getFromDp(2);
//	for (int i = 1; i <= n; ++i) cout << i << " "<< a[i] << " " << b[i] << endl;
	cout << ans + 1 << endl;
}
int main()
{
	cin.sync_with_stdio(0);
	init();
	solve();
}

Compiler output:
a.cc: In function 'void getRoot(int, int)':
a.cc:82:9: error: reference to 'size' is ambiguous
   82 |         size[u] = 1;
      |         ^~~~
In file included from /usr/include/c++/14/string:53,
                 from /usr/include/c++/14/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:52,
                 from a.cc:1:
/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:16:5: note:                 'int size [1000008]'
   16 | int size[N], sizeMax[N];
      |     ^~~~
a.cc:88:17: error: reference to 'size' is ambiguous
   88 |                 size[u] += size[v];
      |                 ^~~~
/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:16:5: note:                 'int size [1000008]'
   16 | int size[N], sizeMax[N];
      |     ^~~~
a.cc:88:28: error: reference to 'size' is ambiguous
   88 |                 size[u] += size[v];
      |                            ^~~~
/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:16:5: note:                 'int size [1000008]'
   16 | int size[N], sizeMax[N];
      |     ^~~~
a.cc:89:46: error: reference to 'size' is ambiguous
   89 |                 sizeMax[u] = max(sizeMax[u], size[v]);
      |                                              ^~~~
/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:16:5: note:                 'int size [1000008]'
   16 | int size[N], sizeMax[N];
      |     ^~~~
a.cc:91:44: error: reference to 'size' is ambiguous
   91 |         sizeMax[u] = max(sizeMax[u], tot - size[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:16:5: note:                 'int size [1000008]'
   16 | int size[N], sizeMax[N];
      |     ^~~~
a.cc: In function 'void work(int)':
a.cc:164:23: error: reference to 'size' is ambiguous
  164 |                 tot = size[v]; root = 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:16:5: note:                 'int size [1000008]'
   16 | int size[N], sizeMax[N];
      |     ^~~~