Problem: Example

Input

5
5 8 1 3 5
1 2 4
2 3 3
2 4 3
1 5 7


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

#define N 100010
#define inf 0x3f3f3f3f

using namespace std;

struct lhy{
	int x, y, l, next;
}edge[N << 1];

int tot, ans, n, l, nowsize, root, g[N], flag[N], nowl, newl;
pair<long long, int> q[N], Q[N];
int son[N], size[N], Max[N];

set<pair<long long, int> >A;
set<pair<long long, int> >::iterator it;

inline void adde(int x, int y, int l)
{
	edge[++tot].x = x; edge[tot].y = y; edge[tot].l = l; edge[tot].next = son[x]; son[x] = tot;
}

void GetRoot(int x, int fa)
{
	size[x] = 1;
	Max[x] = 0;
	for(int i = son[x]; i; i = edge[i].next)
	{
		int y = edge[i].y;
		if(flag[y] || y == fa)continue;
		GetRoot(y, x);
		size[x] += size[y];
		Max[x] = max(Max[x], size[y]);
	}
	Max[x] = max(Max[x], nowsize - size[x]);
	if(Max[x] < Max[root])root = x;
}

void ask(long long v, int deep)
{
	it = A.upper_bound(make_pair(v, inf));
	it--;
	if((*it).first == - 1ll * inf * inf)return;
	//printf("%d %d\n", (*it).first, v);
	ans = max(ans, deep + (*it).second - 1);
}
int CNT;
void add(long long v, int deep)
{
	it = A.upper_bound(make_pair(v, inf));
	it--;
	if((*it).second >= deep)return;
	it++;
	set<pair<long long, int> >::iterator it2 = it, it1;
	for(; it2 != A.end(); it2++)
	{
		if((*it2).second > deep)break;
	}
	while(it != it2)
	{
		it1 = it;
		it++;
		A.erase(it1);
		CNT++;
	}
	A.insert(make_pair(v, deep));
}

void dfs(int x, int fa, long long sumg, long long suml, int deep, long long nowmin1, long long nowmin2)
{
	long long nowv = sumg - suml;
	//printf("%d %lld %lld %lld\n", x, nowmin1, nowmin2, nowv);
	if(nowmin2 >= 0)
	{
		ans = max(ans, nowl + deep - 1);
		ask(nowv, deep);
		//printf("!%d\n", ans);
	}
	if(nowmin1 < 0)
	{
		q[++l] = make_pair(-nowmin1, deep);
	}
	else
	{
		newl = max(newl, deep);
	}
	for(int i = son[x]; i; i = edge[i].next)
	{
		int y = edge[i].y;
		if(flag[y] || y == fa)continue;
		dfs(y, x, sumg + g[y], suml + edge[i].l, deep + 1, min(nowmin1, sumg - suml + g[root] - edge[i].l), min(nowmin2 + g[y] - edge[i].l, 0ll + g[y] - edge[i].l));
	}
}

void work(int x)
{
	int L = 0;
	nowl = 1;
	for(int i = son[x]; i; i = edge[i].next)
	{
		int y = edge[i].y;
		newl = 1;
		l = 0;
		if(flag[y])continue;
		dfs(y, x, g[y], edge[i].l, 2, g[x] - edge[i].l, g[y] - edge[i].l);
		CNT = 0;
		//printf("%d\n", l);
		for(int j = 1; j <= l; j++)
			add(q[j].first, q[j].second);
		//printf("%d\n", CNT);
		//printf("%d\n", A.size());
		Q[++L] = make_pair(y, edge[i].l);
		nowl = max(nowl, newl);
		ans = max(ans, nowl);
	}
	A.clear();
	A.insert(make_pair(-1ll * inf * inf, -inf));
	A.insert(make_pair(1ll * inf * inf, inf));
	nowl = 1;
	for(int i = L; i; i--)
	{
		int y = Q[i].first;
		newl = 1;
		l = 0;
		dfs(y, x, g[y], Q[i].second, 2, g[x] - Q[i].second, g[y] - Q[i].second);
		for(int j = 1; j <= l; j++)
			add(q[j].first, q[j].second);
		nowl = max(nowl, newl);
		ans = max(ans, nowl);
	}
	A.clear();
	A.insert(make_pair(-1ll * inf * inf, -inf));
	A.insert(make_pair(1ll * inf * inf, inf));
}

void Divide(int x)
{
	flag[x] = 1;
	//printf("--%d\n", x);
	work(x);
	//printf("%d\n", ans);
	for(int i = son[x]; i; i = edge[i].next)
	{
		int y = edge[i].y;
		if(flag[y])continue;
		root = 0;
		nowsize = size[y];
		GetRoot(y, 0);
		Divide(root);
	}
	//printf("--%d\n", x);
}

int main()
{
	A.insert(make_pair(-1ll * inf * inf, -inf));
	A.insert(make_pair(1ll * inf * inf, inf));
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &g[i]);
	for(int i = 1; i < n; i++)
	{
		int x, y, l;
		scanf("%d%d%d", &x, &y, &l);
		adde(x, y, l);
		adde(y, x, l);
	}
	ans = 1;
	Max[0] = n + 1;
	root = 0;
	nowsize = n;
	GetRoot(1, 0);
	Divide(root);
	printf("%d\n", ans);
}