记录编号	170031	评测结果	AAAAAAAAA
题目名称	[TJOI 2015] 旅游	最终得分	100
用户昵称	thomount	是否通过	通过
代码语言	C++	运行时间	1.892 s
提交时间	2015-07-12 00:46:07	内存使用	2.63 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int read() {
	char ch = getchar();
	while (ch < '0' || ch > '9') ch = getchar();
	int ans = 0;
	while (ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0', ch = getchar();
	return ans;
}

const int ml = 2147480000;
struct point {
	int x, maxn, minn, maxd[2], plus, rev, t;
	point *s[2], * f;
	
	point(int x = 0, int t = 0): x(x), maxn(x), minn(x), plus(0), rev(0), f(0), t(t) {
		maxd[0] = maxd[1] = 0; 
		s[0] = s[1] = 0;
	}
	
	void add(int k) {
		plus += k;
		x += k;
		maxn += k;
		minn += k;
	}
	
	void push() {
		if (plus) {
			if (s[0]) s[0]->add(plus);
			if (s[1]) s[1]->add(plus);
			plus = 0;
		}
		if (rev) {
			swap(s[0], s[1]);
			if (s[0]) {
				swap(s[0]->maxd[0], s[0]->maxd[1]);
				s[0]->rev ^= 1;
			}
			if (s[1]) {
				swap(s[1]->maxd[0], s[1]->maxd[1]);
				s[1]->rev ^= 1;
			}	
			rev = 0;
		}
	}
	
	void update() {
		maxn = x, minn = x;
		maxd[0] = maxd[1] = 0;
		for (int i = 0; i < 2; i++) if (s[i]) {maxn = max(maxn, s[i]->maxn), minn = min(minn, s[i]->minn);}
		
		if (s[0]) {
			for (int i = 0; i < 2; i++) maxd[i] = max(maxd[i], s[0]->maxd[i]);
			maxd[1] = max(maxd[1], s[0]->maxn - x);
			maxd[0] = max(maxd[0], x - s[0]->minn);
		}
		
		if (s[1]) {
			for (int i = 0; i < 2; i++) maxd[i] = max(maxd[i], s[1]->maxd[i]);
			maxd[0] = max(maxd[0], s[1]->maxn - x);
			maxd[1] = max(maxd[1], x - s[1]->minn);
		}
		
		if (s[0] && s[1]) {
			maxd[0] = max(maxd[0], s[1]->maxn - s[0]->minn);
			maxd[1] = max(maxd[1], s[0]->maxn - s[1]->minn);
		}
	}
	
	bool isroot() {
		if (!f || (f->s[0] != this && f->s[1] != this)) return true; else return false;
	}
	
	int getw() {
		if (isroot()) return -1; else return (f->s[0] == this)?0:1;
	}
	
	void match(point * p, int k) {
		if (k >= 0) s[k] = p; if (p) p->f = this; update();
	}
	
	void rotate() {
		point * f1 = f; point * ff = f1->f;
		int k1 = getw(), k2 = f1->getw();
		f1->match(s[k1^1], k1);
		match(f1, 1^k1);
		if (ff) ff->match(this, k2); else f = 0;
	}
} d[50010];

typedef point * link;
link p[50010];
int tot = 0;
link make(int x, int t) {
	d[++tot] = point(x, t);
	return &d[tot];
}

link q[50010];
void splay(link p) {
	link p1 = p;
	int r = 1; q[r] = p1;
	while (!p1->isroot()) p1 = q[++r] = p1->f;
	for (int i = r; i; i--) q[i]->push();
	
	while (!p->isroot() && !p->f->isroot()) {
		if (p->getw() == p->f->getw()) p->f->rotate(); else p->rotate();
		p->rotate();
	}
	
	if (!p->isroot()) p->rotate();
}

void access(link p) {
	link q = 0;
	while (p) {
		splay(p);
		p->match(q, 1);
		q = p; p = p->f;
	}
}

void connect(link p1, link p2) {
	access(p2); splay(p2);
	p2->rev ^= 1; swap(p2->maxd[0], p2->maxd[1]);
	access(p1); splay(p1);
	p1->match(p2, -1);
}

int price[50010];

int main() {
	freopen("tjoi2015_travel.in", "r", stdin);
	freopen("tjoi2015_travel.out", "w", stdout);
	int n = read();
	for (int i = 1; i <= n; i++) {
		price[i] = read();
		p[i] = make(price[i], i);
	}
	for (int i = 1; i < n; i++) {
		int x = read(), y = read();
		connect(p[x], p[y]);
	}
	
	int m = read();
	for (int i = 1; i <= m; i++) {
		int x = read(), y = read(), rise = read();
		if (x == y) {
			printf("0\n");
			p[x]->x += rise; p[x]->update();
			access(p[x]); splay(p[x]);
			continue;
		}
		access(p[x]); splay(p[x]); 
		p[x]->rev ^= 1; 
		swap(p[x]->maxd[0], p[x]->maxd[1]);
		
		access(p[y]); splay(p[x]);
		p[x]->s[1]->f = 0; p[x]->s[1] = 0;
		splay(p[y]);
		 
		int ans = 0;
		link pp = p[y]->s[0];
		int max1 = 0, min1 = ml;
		if (pp) {ans = max(ans, pp->maxd[0]); max1 = pp->maxn; min1 = pp->minn; pp->add(rise);}
		ans = max(ans, max(max1, p[y]->x) - p[x]->x);
		ans = max(ans, p[y]->x - min(min1, p[x]->x));
		printf("%d\n", ans);
		p[x]->x += rise; p[x]->update();
		p[y]->x += rise; p[y]->update();
		p[x]->match(p[y], 1);
	}
	return 0;
}