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 <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <ctime>
using namespace std;


#define N 200100
#define M 2000010
#define ULL unsigned long long
#define LL long long
#define ls (i << 1)
#define rs (ls | 1)
#define md ((ll + rr) >> 1)
#define lson ll, md, ls
#define rson md + 1, rr, rs
#define inf 0x3f3f3f3f
#define eps 1e-4
#define pii pair<int, int>
#define MP make_pair
#define mod 1000000007

int fst[N], vv[M], nxt[M], cost[M], e;
int dep[N];
int sz[N], root, tot, Mx;
int g[N];
bool vis[N];
vector<pii> from[N], to[N];
int ans;
void init() {
	memset(fst, -1, sizeof fst);
	e = 0;
}

void add(int u, int v, int w) {
	vv[e] = v, cost[e] = w, nxt[e] = fst[u], fst[u] = e++;
}

void dfs1(int u, int p) {
	sz[u] = 1;
	for(int i = fst[u]; ~i; i = nxt[i]) {
		int v = vv[i];
		if(v == p || vis[v]) continue;
		dfs1(v, u);
		sz[u] += sz[v];
	}
}

void dfs2(int u, int p) {
	int mx = tot-sz[u];
	for(int i = fst[u]; ~i; i = nxt[i]) {
		int v = vv[i];
		if(v == p || vis[v]) continue;
		dfs2(v, u);
		mx = max(mx, sz[v]);
	}
	if(mx < Mx) {
		Mx = mx, root = u;
	}
}
void find_root(int &u) {
	dfs1(u, 0);
	Mx = inf;
	tot = sz[u];
	dfs2(u, 0);
	u = root;
}

int san[N], scnt;
void dfsf(int u, int p, int id, int need, int rest) {
	if(need == 0) {
		from[id].push_back(MP(rest,dep[u]));
		san[scnt++] = rest;
	}
	for(int i = fst[u]; ~i; i = nxt[i]) {
		int v = vv[i];
		if(v == p || vis[v]) continue;
		int nxt = need;
		if(g[v] >= cost[i]) 
			nxt = max(0, need - (g[v]-cost[i]));
		else nxt = need + cost[i]-g[v];
		dfsf(v, u, id, nxt, rest + g[v] - cost[i]);
	}
}
void dfst(int u, int p, int id, int need, int more) {
	to[id].push_back(MP(need, dep[u]));
	san[scnt++] = need;
	for(int i = fst[u]; ~i; i = nxt[i]) {
		int v = vv[i];
		if(v == p || vis[v]) continue;
		int nxt = max(0, cost[i] - g[u]);
		int cut = min(nxt, more);
		dfst(v, u, id, need + nxt - cut, more + max(0, g[u] - cost[i]) - cut);
	}
}
void dfs(int u, int p) {
	dep[u] = dep[p] + 1;
	for(int i = fst[u]; ~i; i = nxt[i]) {
		int v = vv[i];
		if(v == p || vis[v]) continue;
		dfs(v, u);
	}
}

int mxv[N];
void add(int x, int v) {
	while(x) {
		mxv[x] = max(mxv[x], v);
		x -= x & -x;
	}
}
int query(int x) {
	int ans = -1;
	while(x <= scnt) {
		ans = max(ans, mxv[x]);
		x += x & -x;
	}
	return ans;
}

int find(int x) {
	return lower_bound(san, san+scnt, x) - san + 1;
}
void gao(int i) {
	for(int j = 0; j < to[i].size(); ++j) {
		pii cur = to[i][j];
		if(cur.first == 0) ans = max(ans, cur.second);
		int tmp = query(find(cur.first));
		if(tmp != -1)
			ans = max(ans, tmp+cur.second-1);
	}
	for(int j = 0; j < from[i].size(); ++j) {
		pii cur = from[i][j];
		ans = max(cur.second, ans);
		add(find(cur.first), cur.second);
	}
}
void solve(int u) {
	find_root(u);
	vis[u] = 1;
	dfs(u, 0);
	int cnt = 0;
	scnt = 0;
	for(int i = fst[u]; ~i; i = nxt[i]) {
		int v = vv[i];
		if(vis[v]) continue;
		++cnt;
		from[cnt].clear(); to[cnt].clear();
		dfsf(v, u, cnt, max(0,cost[i]-g[v]), g[v]-cost[i]);
		dfst(v, u, cnt, max(0, cost[i]-g[u]), max(0, g[u] - cost[i]));
	}
	sort(san, san+scnt);
	scnt = unique(san, san+scnt) - san;
	for(int i = 1; i <= scnt; ++i) mxv[i] = -1;
	for(int i = 1; i <= cnt; ++i) gao(i);
	for(int i = 1; i <= scnt; ++i) mxv[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(vis[v]) continue;
		solve(v);
	}
}
int main() {
	int n;
	scanf("%d", &n);
	init();
	for(int i = 1; i <= n; ++i) scanf("%d", &g[i]);
	for(int i = 1; i < n; ++i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		add(u, v, w);
		add(v, u, w);
	}
	ans = 1;
	solve(1);
	printf("%d\n", ans);
}