记录编号	162636	评测结果	AAAAAAAAA
题目名称	[TJOI 2015] 旅游	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	1.899 s
提交时间	2015-05-18 13:59:03	内存使用	5.44 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>

#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define mv(x) tree[x].mv
#define rmv(x) tree[x].rmv
#define maxv(x) tree[x].maxv
#define minv(x) tree[x].minv
#define addv(x) addv[x]
#define N 50010
#define MP(x,y) make_pair(x,y)
#define fir first
#define sec second
#define INF 0x3f3f3f3f

using namespace std;

void file(){
	freopen("tjoi2015_travel.in","r",stdin);
	freopen("tjoi2015_travel.out","w",stdout);
}

struct node{
	int mv,maxv,minv;
	int rmv;
	void init(){
		rmv=mv=0;
		maxv=0;
		minv=INF;
	}
}tree[N<<1];

node reverse(node x){
	swap(x.rmv,x.mv);
	return x;
}

node operator+(const node &a,const node &b){
	node c;
	c.rmv=max(a.rmv,b.rmv);
	c.rmv=max(c.rmv,a.maxv-b.minv);
	c.mv=max(a.mv,b.mv);
	c.mv=max(c.mv,b.maxv-a.minv);
	c.minv=min(a.minv,b.minv);
	c.maxv=max(a.maxv,b.maxv);
	return c;
}

int ch[N<<1][2],tot,tot_n,pos[N],addv[N<<1];

void update(int x){
	if(!l(x)) return;
	tree[x]=tree[l(x)]+tree[r(x)];
}

int build(int src[],int l,int r){
	int x=++tot;
	addv(x)=0;
	if(l==r){
		maxv(x)=minv(x)=src[pos[l]];
		mv(x)=rmv(x)=0;
		return x;
	}
	int mid=(l+r)>>1;
	l(x)=build(src,l,mid);
	r(x)=build(src,mid+1,r);
	update(x);
	return x;
}

void push(int x){
	if(!addv(x)||!l(x)) return;
	addv(l(x))+=addv(x);
	maxv(l(x))+=addv(x);
	minv(l(x))+=addv(x);
	addv(r(x))+=addv(x);
	maxv(r(x))+=addv(x);
	minv(r(x))+=addv(x);
	addv(x)=0;
}

node ask(int o,int l,int r,int ql,int qr){
	push(o);
	if(ql<=l&&r<=qr){
		return tree[o];
	}
	int mid=(l+r)>>1;
	if(ql<=mid&&mid<qr){
		node lc=ask(l(o),l,mid,ql,qr);
		node rc=ask(r(o),mid+1,r,ql,qr);
		update(o);
		return lc+rc;
	}
	if(ql<=mid){
		node lc=ask(l(o),l,mid,ql,qr);
		update(o);
		return lc;
	}
	if(mid<qr){
		node rc=ask(r(o),mid+1,r,ql,qr);
		update(o);
		return rc;
	}
}

void addin(int o,int l,int r,int ql,int qr,int qv){
	push(o);
	if(ql<=l&&r<=qr){
		addv(o)+=qv;
		maxv(o)+=qv;
		minv(o)+=qv;
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) addin(l(o),l,mid,ql,qr,qv);
	if(mid<qr) addin(r(o),mid+1,r,ql,qr,qv);
	update(o);
}

struct edge{
	int x,to;
}E[N<<1];

int n,m,top[N],fa[N],L[N],d[N],g[N],totE,siz[N],h[N],tott,a[N];

void ade(int x,int y){
	E[++totE]=(edge){y,g[x]}; g[x]=totE;
}

#define p E[i].x

void dfs1(int x){
	siz[x]=1;
	for(int i=g[x];i;i=E[i].to)
		if(p!=fa[x]){
			d[p]=d[x]+1;
			fa[p]=x;
			dfs1(p);
			siz[x]+=siz[p];
			if(siz[p]>siz[h[x]]) h[x]=p;
		}
}

void dfs2(int x,int tp){
	top[x]=tp; L[x]=++tott; pos[tott]=x;
	if(h[x]) dfs2(h[x],tp);
	for(int i=g[x];i;i=E[i].to)
		if(p!=fa[x]&&p!=h[x]) dfs2(p,p);
}

int com_ask(int u,int v){
	int f1=top[u],f2=top[v];
	tot_n=0;
	node ls,rs;
	ls.init(); rs.init();
	while(f1!=f2){
		if(d[f1]>=d[f2]){
			ls=ask(1,1,n,L[f1],L[u])+ls;
			u=fa[f1],f1=top[u];
		}
		else{
			rs=ask(1,1,n,L[f2],L[v])+rs;
			v=fa[f2],f2=top[v];
		}
	}
	ls=reverse(ls);
	if(d[u]<=d[v])	ls=ls+ask(1,1,n,L[u],L[v]);
	else rs=reverse(ask(1,1,n,L[v],L[u]))+rs;
	node ans=ls+rs;
	return ans.mv;
}

void com_add(int u,int v,int w){
	int f1=top[u],f2=top[v];
	while(f1!=f2){
		if(d[f1]<d[f2]) swap(f1,f2),swap(u,v);
		addin(1,1,n,L[f1],L[u],w);
		u=fa[f1]; f1=top[u];
	}
	if(L[u]>L[v]) swap(u,v);
	addin(1,1,n,L[u],L[v],w);
}

int main(){
	file();
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		ade(x,y); ade(y,x);
	}
	d[1]=1;
	dfs1(1); dfs2(1,1);
	build(a,1,n);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		com_add(x,y,z);
		printf("%d\n",com_ask(x,y));
	}
	return 0;
}