记录编号	162537	评测结果	AAAAAAAAA
题目名称	[TJOI 2015] 旅游	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.923 s
提交时间	2015-05-17 17:34:36	内存使用	7.22 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
//#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 50002, INF = 0x3f3f3f3f;

int N;
int top[maxn], dep[maxn], id[maxn], seq[maxn], val[maxn], size[maxn], p[maxn], son[maxn];

#include <vector>
vector<int> adj[maxn];

struct Data{
	int md, rmd, Min, Max;
	inline void init(){md = rmd = Max = 0, Min = INF;}
	inline void init(int v){md = rmd = 0, Min = Max = v;}
};
inline Data operator + (const Data &a, const Data &b){
	int md, rmd, Min, Max;
	Min = min(a.Min, b.Min);
	Max = max(a.Max, b.Max);
	md = max(b.Max - a.Min, max(a.md, b.md));
	rmd = max(a.Max - b.Min, max(a.rmd, b.rmd));
	return (Data){md, rmd, Min, Max};
}
inline Data rev(const Data &x){
	Data ans = x;
	swap(ans.md, ans.rmd);
	return ans;
}
inline void operator += (Data &a, int d){a.Min += d, a.Max += d;}

struct SegT{
	Data dt;
	int L, R, mid, tag;
	SegT *ls, *rs;
	inline void push(){
		if(ls)ls->tag += tag, rs->tag += tag, ls->dt += tag, rs->dt += tag;
		tag = 0;
	}
	void init(int, int);
	void Add(int l, int r, int d){
		if(tag)push();
		if(L == l && R == r){
			dt += d;
			tag += d;
			return;
		}
		if(r <= mid)ls->Add(l, r, d);
		else if(l >= mid)rs->Add(l, r, d);
		else ls->Add(l, mid, d), rs->Add(mid, r, d);
		dt = ls->dt + rs->dt;
	}
	Data Query(int l, int r){
		if(tag)push();
		if(L == l && R == r)return dt;
		if(r <= mid)return ls->Query(l, r);
		if(l >= mid)return rs->Query(l, r);
		return ls->Query(l, mid) + rs->Query(mid, r);
	}
}T[maxn * 3], *iter = T + maxn - 1;

void SegT::init(int l, int r){
	L = l, R = r;mid = (l + r) >> 1;
	if(l == mid){
		dt.init(seq[l]);
		return;
	}
	ls = ++iter;ls->init(l, mid);
	rs = ++iter;rs->init(mid, r);
	dt = ls->dt + rs->dt;
}

void dfs(int cur){
	vector<int>::iterator it;
	int to, maxs = 0, hs;
	size[cur] = 1;
	for(it = adj[cur].begin();it != adj[cur].end();++it)if((to = *it) != p[cur]){
		dep[to] = dep[cur] + 1;
		p[to] = cur;
		dfs(to);
		if(size[to] > maxs)maxs = size[to], hs = to;
		size[cur] += size[to];
	}
	if(maxs)son[cur] = hs;
}

void build(int cur, int ind){
	vector<int>::iterator it;
	int to, s;
	seq[id[cur] = ind++] = val[cur];
	if((s = son[cur])){
		top[s] = top[cur];
		build(s, ind);
	}
	else T[top[cur]].init(0, ind);

	for(it = adj[cur].begin();it != adj[cur].end();++it)if((to = *it) != p[cur] && to != s){
		ind = 0;
		top[to] = to;
		build(to, 0);
	}
}

inline void init(){
	getd(N);
	int i, u, v;
	for(i = 1;i <= N;++i)getd(val[i]);
	for(i = 1;i < N;++i){
		getd(u), getd(v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dep[1] = 1;dfs(1);
	top[1] = 1;build(1, 0);
}

inline void work(){
	int Q, u, v, a, b, d;getd(Q);
	Data s, t, mid;
	while(Q--){
		getd(u), getd(v), getd(d);
		s.init(), t = s;
		a = top[u], b = top[v];
		while(a != b){
			if(dep[a] <= dep[b]){
				T[b].Add(id[b], id[v]+1, d);
				t = T[b].Query(id[b], id[v]+1) + t;
				v = p[b];b = top[v];
			}
			else{
				T[a].Add(id[a], id[u]+1, d);
				s = T[a].Query(id[a], id[u]+1) + s;
				u = p[a];a = top[u];
			}
		}
		if(dep[u] <= dep[v])T[a].Add(id[u], id[v]+1, d), mid = T[a].Query(id[u], id[v] + 1);
		else T[a].Add(id[v], id[u]+1, d), mid = rev(T[a].Query(id[v], id[u] + 1));
		s = (rev(s) + mid + t);
		printf("%d\n", s.md);
	}
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(tjoi2015_travel);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	init();
	work();

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}