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 LL long long
#define N 111111
using namespace std;
const int debug=0;
int n,i,x,y,z,an,tot,a[N],fir[N],la[N*2],ne[N*2],va[N*2],sz[N],mv[N],q[N],E[N];
bool vis[N];
LL V[N*3];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;va[tot]=z;}
void bd(int k,int l,int r){
	V[k]=-1e18;
	if(l==r)return;
	int md=l+r>>1;
	bd(k<<1,l,md);bd(k<<1|1,md+1,r);
}
void add(int k,int l,int r,int x,LL z){
	V[k]=max(V[k],z);
	if(l==r)return;
	int md=l+r>>1;
	if(x<=md)add(k<<1,l,md,x,z);else add(k<<1|1,md+1,r,x,z);
}
int qu(int k,int l,int r,LL z){
	if(V[k]<z)return -1e9;
	if(l==r)return l;
	int md=l+r>>1;
	if(V[k<<1|1]>=z)return qu(k<<1|1,md+1,r,z);else return qu(k<<1,l,md,z);
}
void dsz(int x,int fa,int dis,int&mx){
	mx=max(mx,dis);
	sz[x]=1;mv[x]=0;
	for(int i=fir[x],y;i;i=ne[i])
		if(!vis[y=la[i]]&&y!=fa)
			dsz(y,x,dis+1,mx),sz[x]+=sz[y],mv[x]=max(mv[x],sz[y]);
}
void drt(int zs,int x,int fa,int&rt){
	mv[x]=max(mv[x],sz[zs]-sz[x]);
	if(mv[x]<mv[rt]||!rt)rt=x;
	for(int i=fir[x],y;i;i=ne[i])
		if(!vis[y=la[i]]&&y!=fa)drt(zs,y,x,rt);
}
void getup(int x,int fa,LL z,LL mi,int dis,int mx){
//	printf("%d %lld \n",x,mi);
	if(mi>=0)add(1,1,mx,dis,z);//,printf("ADD %d %d %lld\n",x,dis,z);
	for(int i=fir[x],y;i;i=ne[i])
		if(!vis[y=la[i]]&&y!=fa)getup(y,x,z-va[i]+a[y],min(mi,0ll)-va[i]+a[y],dis+1,mx);
}
void getdown(int x,int fa,LL z,LL mi,int dis,int mx){
//	printf("%d %lld   %d\n",x,mi,dis);	
	z+=a[x];
	an=max(an,qu(1,1,mx,-mi)+dis+1);//>=-mi de zuidadeshu
	if(mi>=0)an=max(an,dis+1);
	for(int i=fir[x],y;i;i=ne[i])
		if(!vis[y=la[i]]&&y!=fa)getdown(y,x,z-va[i],min(mi,z-va[i]),dis+1,mx);
}
void fz(int x){
	int i,p,y,rt=0,mx=0,t=0;
	dsz(x,0,0,mx);
mx ++;
	drt(x,x,0,rt);
	vis[rt]=1;
//	printf("------%d------\n",rt);
	if(mx){
		bd(1,1,mx);
		for(i=fir[rt];i;i=ne[i])if(!vis[la[i]])q[++t]=la[i],E[t]=va[i];
		for(i=1;i<=t;i++)y=q[i],getdown(y,rt,a[rt]-E[i],a[rt]-E[i],1,mx),getup(y,rt,a[q[i]]-E[i],a[q[i]]-E[i],1,mx);
		an=max(an,qu(1,1,mx,0)+1);
		bd(1,1,mx);
		for(i=t;i;i--)y=q[i],getdown(y,rt,a[rt]-E[i],a[rt]-E[i],1,mx),getup(y,rt,a[q[i]]-E[i],a[q[i]]-E[i],1,mx);
//		printf("%d\n",an);
	}
	for(i=fir[rt];i;i=ne[i])if(!vis[y=la[i]])fz(y);
}
void dfs(int x,int fa,LL z,int w){
	//if(mi>=0){
		an=max(an,w);
	
	//}
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)
		if(z-va[i]>=0)dfs(la[i],x,z-va[i]+a[la[i]],w+1);
}
int main(){
	//srand(time(0));
	an=1;
	if(debug)n=1000;else scanf("%d",&n);
	for(i=1;i<=n;i++)if(debug)a[i]=rand()%20+1,printf("%d ",a[i]);else scanf("%d",&a[i]);
	//puts("");
	for(i=1;i<n;i++){
		if(debug){
			x=rand()%i+1;
			y=i+1;
			z=rand()%20+1;
			printf("%d %d %d\n",x,y,z);
		}else scanf("%d%d%d",&x,&y,&z);
		ins(x,y,z),ins(y,x,z);
	}
/*	for(i=1;i<=n;i++){
		dfs(i,0,a[i],1);
		memset(vis,0,sizeof vis);
	}
	printf("%d\n",an);
	an=0;*/
	fz(1);
	printf("%d\n",an);
}