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 <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

#define debug(x) cerr<<#x<<'='<<x<<'\n'
#define Int const int &

const int N=110000;

struct edge {
	int v, nxt, w;
} e[N<<1];

bool pd[N];
int first[N], g[N], sz[N];
int n, tot, where, now, ans;
struct atom {
	int where, w;
	long long f;
	//??´???????????(??????)¶?×?£¬????(????????????)£¬?£????????/??????????×??????£ 
};
vector<atom> A, B;
inline void add(Int f, Int t, Int l) {
	e[++tot]=(edge){t, first[f], l};
	first[f]=tot;
}
void make_sz(int k, int f) { //´???×??÷´??? 
	sz[k]=1;
	for (int j=first[k]; j; j=e[j].nxt) {
		int s=e[j].v;
		if (pd[s]==0 && s!=f) {
			make_sz(s, k);
			sz[k]+=sz[s];
		}
	}
}
void make_c(int k, int f) { //?????? °???????±???´???±???where 
	int num=n-sz[k];
	for (int j=first[k]; j; j=e[j].nxt) {
		if (!pd[e[j].v] && e[j].v!=f) {
			num=max(num, sz[e[j].v]);
			make_c(e[j].v, k);
		}
	}
	if (num<now) {
		now=num;
		where=k;
	}
}
void dfs3(int k, int f, long long dis, long long mn, int sz, int w) {
//?±?°????£¬??????£¬?£????????£¬×??????????£??????×?????£¬×???????????£¬????????(??????)¶?×??£ 
	dis+=g[k];
	mn+=g[k];
	mn=min(mn, 0ll); 
	if (mn>=0) { //????????dfs????´???????×???????£¬?????¬????×????????????????±????0??min?¢??????0?????????? 
		A.push_back((atom){w, sz, dis});
	}
	for (int j=first[k]; j; j=e[j].nxt) {
		if (e[j].v!=f && pd[e[j].v]==false) {
			dfs3(e[j].v, k, dis-e[j].w, mn-e[j].w, sz+1, w);
		}
	}
}
void dfs4(int k, int f, long long dis, long long mn, int sz, int w) {
	mn=min(mn, dis); dis+=g[k];
	B.push_back((atom){w, sz, mn});
	for (int j=first[k]; j; j=e[j].nxt) {
		if (e[j].v!=f && pd[e[j].v]==false) {
			dfs4(e[j].v, k, dis-e[j].w, mn, sz+1, w);
		}
	}
}
inline bool cmp(const atom &k1, const atom &k2) {
	return k1.f<k2.f;
}
void solve(int k) {
	make_sz(k, 0);
	n=sz[k];
	now=n+1;
	where=0;
	make_c(k, 0);
	pd[where]=true;
	A.clear(); B.clear();
	A.push_back((atom){where, 1, g[k]});
	B.push_back((atom){where, 0, 0});
	for (int j=first[where]; j; j=e[j].nxt) {
		if (pd[e[j].v]==0) { //×¢?????????¶´??????±×?????????????´?¶?×?????×? 
			dfs3(e[j].v, where, g[where]-e[j].w, -e[j].w, 2, e[j].v);
			dfs4(e[j].v, where, -e[j].w, -e[j].w, 1, e[j].v);
		}
	}
	sort(A.begin(), A.end(), cmp); //?£??????´??????????? 
	sort(B.begin(), B.end(), cmp); //×??????????£??????×?????´??????????? 
	int lw=where;
	int now=A.size()-1, where=0, f=-1e9, g=-1e9; //g??×?´???£¬f?? ??????¶?×????±?××?´??????????????? ????????×?´??? 
	for (int i=0; i<B.size(); i++) {
		while (now>=0 && A[now].f+B[i].f>=0) {
			int k1=A[now].where;
			if (k1==where) {
   			    f=max(f, A[now].w);
			} else {
			    if (A[now].w>f) {
			    	where=A[now].where;
			    	g=f;
			    	f=A[now].w;
			    } else {
			    	g=max(g, A[now].w);
			    }
			}
			now--;
		}
		if (B[i].where==where) {
			ans=max(ans, g+B[i].w);
		} else {
			ans=max(ans, f+B[i].w);
		}
	}
	for (int j=first[lw]; j; j=e[j].nxt) {
		if (pd[e[j].v]) continue;
		solve(e[j].v);
	}
}
inline void read(int &p) {
	char c=getchar();
	while (c<48 || c>57) {
		c=getchar();
	}
	p=0;
	while (c>47 && c<58) {
		p=p*10+c-48;
		c=getchar();
	}
}
int main(void) {
	read(n);
	for (int i=1; i<=n; i++) {
		read(g[i]);
	}
	for (int i=1, f, t, w; i<n; i++) {
		read(f); read(t); read(w);
		add(f, t, w);
  		add(t, f, w);
  	}
  	ans=1;
  	solve(1);
  	printf("%d\n", ans);
  	return 0;
  }