记录编号	162600	评测结果	AAAAAAAAA
题目名称	[TJOI 2015] 旅游	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.894 s
提交时间	2015-05-18 08:41:51	内存使用	3.20 MiB

/****************************************\
* Author : ztx
* Title  : 
[cogs] 1978. [TJOI2015]旅游
[bzoj] 3999: [TJOI2015]旅游
* ALG    : LCT
不可以写换根的 QAQ
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
	ret[0]=0;while (CH=getchar() , CH<'!') ;
	while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;
	ret[ret[0]+1]=0;
}

#define  maxt  50010LL

int fa[maxt] = {0} , ch[2][maxt] = {0} ;

#define  f(o)  fa[o]
#define  l(o)  ch[0][o]
#define  r(o)  ch[1][o]
#define  null  0LL
#define  infi  0x3f3f3f3fLL
#define  min(x,y) ((x)<(y)?(x):(y))
#define  max(x,y) ((x)>(y)?(x):(y))

bool turn[maxt] ;
int add[maxt] = {0} , val[maxt] , maxv[maxt] , minv[maxt] , maxp_d[maxt] , maxp_u[maxt] ;
/* maxp_d  up->down  maxp_u down->up */
inline bool Isrt(int u) { return !f(u)||(l(f(u))!=u&&r(f(u))!=u) ; }
inline void Exchange(int&a,int&b) { int c=a;a=b;b=c; }
inline void ADD(int u,int w) {
	if (!u) return ;
	add[u] += w ;
	val[u] += w ;
	maxv[u] += w ;
	minv[u] += w ;
}
inline void Clear(int u) {
	if (!u) return ;
	if (add[u])
		ADD(l(u),add[u]) ,
		ADD(r(u),add[u]) ,
		add[u] = 0 ;
	if (turn[u])
		turn[l(u)] ^= 1 ,
		turn[r(u)] ^= 1 ,
		turn[u] = 0 ,
		Exchange(l(u),r(u)) ;
}
inline void Maintain(int u) {
	/*
	从上往下走对应到LCT中是从左儿子走到右儿子
	*/
	if (!u) return ;
	maxv[u] = minv[u] = val[u] ;
	maxp_d[u] = maxp_u[u] = 0 ;
	if (l(u)) {
		maxv[u] = max(maxv[u],maxv[l(u)]) ;
		minv[u] = min(minv[u],minv[l(u)]) ;
		maxp_d[u] = max(maxp_d[u],maxp_d[l(u)]) ;
		maxp_d[u] = max(maxp_d[u],val[u]-minv[l(u)]) ;
		maxp_u[u] = max(maxp_u[u],maxp_u[l(u)]) ;
		maxp_u[u] = max(maxp_u[u],maxv[l(u)]-val[u]) ;
	}
	if (r(u)) {
		maxv[u] = max(maxv[u],maxv[r(u)]) ;
		minv[u] = min(minv[u],minv[r(u)]) ;
		maxp_d[u] = max(maxp_d[u],maxp_d[r(u)]) ;
		maxp_d[u] = max(maxp_d[u],maxv[r(u)]-val[u]) ;
		maxp_u[u] = max(maxp_u[u],maxp_u[r(u)]) ;
		maxp_u[u] = max(maxp_u[u],val[u]-minv[r(u)]) ;
	}
	if (l(u) && r(u)) {
		maxp_d[u] = max(maxp_d[u],maxv[r(u)]-minv[l(u)]) ;
		maxp_u[u] = max(maxp_u[u],maxv[l(u)]-minv[r(u)]) ;
	}
}
inline void Rot(int x,int d) {
	int y=f(x),z=f(y) ;
	if (l(z)==y) l(z)=x ;
	else if (r(z)==y) r(z)=x ;
	f(x)=z,f(y)=x,f(ch[d][x])=y;
	ch[!d][y]=ch[d][x],ch[d][x]=y;
	Maintain(y);
}
inline void Splay(int x) {
	int y , z ;
	Clear(x) ;
	while (!Isrt(x)) {
		y = f(x) , z = f(y) ;
		Clear(z),Clear(y),Clear(x) ;
		if (Isrt(y)) Rot(x,l(y)==x) ;
		else if (l(z)==y) {
			if (l(y)==x) Rot(y,1) ; else Rot(x,0) ;
			Rot(x,1) ;
		} else {
			if (r(y)==x) Rot(y,0) ; else Rot(x,1) ;
			Rot (x,0) ;
		}
	}
	Maintain(x) ;
}
inline void Access(int u) {
	for (int v=null;u;v=u,u=f(u)) Splay(u),r(u)=v,Maintain(u) ;
}
inline void Query(int u,int v,int w) {
int ans = 0 ;
	Access(v) ;
	for (v=null;u;v=u,u=f(u)) {
		Splay(u);
		if (!f(u)) {
			ans = max(maxp_u[v],maxp_d[r(u)]) ;
			ans = max(ans,max(maxv[r(u)],val[u])-min(minv[v],val[u])) ;
			printf("%d\n", ans) ;
			ADD(v,w) ;
			ADD(r(u),w) ;
			val[u] += w ;
			Maintain(u) ;
			return ;
		}
		r(u) = v , Maintain(u) ;
	}
}

#define  maxn  50010LL
struct FST { int to,next; } e[maxn<<1] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u,int v) { e[++tote].to=v;e[tote].next=star[u];star[u]=tote; }

int q[maxn] = {0} , h , r ;
inline void bfs() {
int u , v , p ;
	h = r = 0 , q[r++] = 1 ;
	while (h < r)
		for (u=q[h++],p=star[u];p;p=e[p].next)
			if (v=e[p].to,v!=f(u))
				f(e[p].to)=u,q[r++]=e[p].to ;
}

int main() {
int n , i , j , Time , u , v , w ;
	#define READ
	#ifdef  READ
		freopen("tjoi2015_travel.in" ,"r",stdin ) ;
		freopen("tjoi2015_travel.out","w",stdout) ;
	#endif
	read(n) ;
	Rep (i,1,n)
		read(val[i]) ,
		maxv[i] = minv[i] = val[i] ;
	maxv[0] = -infi , minv[0] = infi ;
	maxp_d[0] = maxp_u[0] = 0 ;
	rep (i,1,n) {
		read(u),read(v) ;
		AddEdge(u,v) ;
		AddEdge(v,u) ;
	}
	bfs() ;
	for (read(Time);Time-->0;) {
		read(u),read(v),read(w) ;
		Query(u,v,w) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}