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>

using namespace std;

#define LL long long
#define pii pair<int, int>
#define MP make_pair
#define inf 0x3f3f3f3f
#define mod 1000000007
#define eps 1e-12
#define Pi acos(-1.0)
#define N 200050
#define M 400020
#define PB push_back
#define MP make_pair
#define fi first
#define se second

int fst[N], vv[M], nxt[M], cost[M], e;
void init(){
	memset(fst, -1, sizeof fst); e = 0;
}
void add(int u, int v, int c){
	vv[e] = v, nxt[e] = fst[u], cost[e] = c, fst[u] = e++;
}

int dep[N], fa[N], sz[N], mx[N];
int q[N], head, tail, del[N];
int san[N], scnt;
vector<pii> to[N], from[N];
int mx_v[N], ans, g[N], n;
void bfs(int s){
	head = tail = 0;
	q[tail++] = s;
	dep[s] = fa[s] = 0;
	while(head < tail){
		int u = q[head++]; 
		for(int i = fst[u]; ~i; i = nxt[i]){
			int v = vv[i];
			if(v == fa[u] || del[v]) continue;
			dep[v] = dep[u] + 1;
			fa[v] = u;
			q[tail++] = v;
		}
	}
}
int get_rt(int s){
	bfs(s);
	int tmp = inf, ret = s;
	for(int i = tail - 1; i >= 0; --i){
		int u = q[i];
		sz[u] = 1, mx[u] = 0;
		for(int j = fst[u]; ~j; j = nxt[j]){
			int v = vv[j];
			if(v == fa[u] || del[v]) continue;
			mx[u] = max(mx[u], sz[v]);
			sz[u] += sz[v];
		}
		mx[u] = max(mx[u], tail - sz[u]);
		if(mx[u] < tmp)
			tmp = mx[u], ret = u;
	}
	return ret;
}
void dfst(int u, int id, int need, int more){
	to[id].push_back(MP(dep[u], need));
	san[++scnt] = need;
	for(int i = fst[u]; ~i; i = nxt[i]){
		int v = vv[i], c = cost[i];
		if(v == fa[u] || del[v]) continue;
		int nxt = max(0, cost[i] - g[u]);
		int cut = min(nxt, more);
		dfst(v, id, need + nxt - cut, more + max(0, g[u] - c) - cut);
	}
}
void dfsf(int u, int id, int need, int more){
	if(need == 0){
		from[id].push_back(MP(dep[u], more));
		san[++scnt] = more;
	}
	for(int i = fst[u]; ~i; i = nxt[i]){
		int v = vv[i], c = cost[i];
		if(v == fa[u] || del[v]) continue;
		dfsf(v, id, max(0, need + c - g[v]), more + g[v] - c);
	}
}
int haxi(int val){
	return lower_bound(san + 1, san + 1 + scnt, val) - san;
}
void upd(int x, int v){
	for(int i = x; i <= scnt; i += i & -i) 
		mx_v[i] = max(mx_v[i], v);
}
int query(int x){
	int ret = -1;
	for(int i = x; i > 0; i -= i & -i)
		ret = max(ret, mx_v[i]);
	return ret;
}
void gao(int id){
	for(int i = 0; i < from[id].size(); ++i){
		int d1 = from[id][i].first, more = from[id][i].second;
		int d2 = query(haxi(more));
		if(d2 == -1) d2 = 0;
		ans = max(ans, d1 + d2 + 1);
	}
	for(int i = 0; i < to[id].size(); ++i){
		int d1 = to[id][i].first, need = to[id][i].second;
		upd(haxi(need), d1);
		if(need == 0) ans = max(ans, d1 + 1);
	}
}

void div(int s){
	int u = get_rt(s);
	bfs(u);
	del[u] = 1;
	int cnt = 0;
	scnt = 0;
	for(int i = fst[u]; ~i; i = nxt[i]){
		int v = vv[i], c = cost[i];
		if(v == fa[u] || del[v]) continue;
		++cnt;
		to[cnt].clear();
		from[cnt].clear();
		dfst(v, cnt, max(0, c - g[u]), max(0, g[u] - c));
		dfsf(v, cnt, max(0, c - g[v]), g[v] - c);
	}
	sort(san + 1, san + scnt + 1);
	scnt = unique(san + 1, san + 1 + scnt) - san - 1;
	for(int i = 1; i <= scnt; ++i) mx_v[i] = -1;
	for(int i = 1; i <= cnt; ++i) gao(i);
	for(int i = 1; i <= scnt; ++i) mx_v[i] = -1;
	for(int i = cnt; i >= 1; --i) gao(i);
	for(int i = fst[u]; ~i; i = nxt[i]){
		int v = vv[i];
		if(v == fa[u] || del[v]) continue;
		div(v);
	}
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &g[i]);
	init();
	for(int i = 1; i < n; ++i){
		int u, v, c;
		scanf("%d%d%d", &u, &v, &c);
		add(u, v, c);
		add(v, u, c);
	}
	ans = 1;
	div(1);
	printf("%d\n", ans);

	return 0;
}