记录编号 163334 评测结果 AAAAAAAAA
题目名称 1978.[TJOI 2015] 旅游 最终得分 100
用户昵称 thomount 是否通过 通过
代码语言 C++ 运行时间 0.946 s
提交时间 2015-05-23 22:15:21 内存使用 10.02 MiB
显示代码纯文本
#include <cstdio>
#include <cstring>
int read() {
	char ch = getchar();
	int ans = 0;
	while (ch < '0' || ch > '9') ch =getchar();
	while (ch >= '0' && ch <= '9') {
		ans = ans * 10 + ch - '0';
		ch = getchar();
	}
	return ans;
}
struct edge {
	int x, y, next;
	edge(int x = 0, int y = 0, int next = -1): x(x), y(y), next(next) {}
} e[100010];
int tte = 0, h[50010];
void match(int x, int y) {
	e[tte] = edge(x, y, h[x]); h[x] = tte++;
	e[tte] = edge(y, x, h[y]); h[y] = tte++;
}
int head, f[50010], son[50010], par[50010], size[50010], dp[50010], price[50010], price1[50010];
void dfs1(int x, int father) {
	int p = h[x];
	f[x] = father; dp[x] = dp[father] + 1;
	son[x] = 0;
	size[x] = 1;
	while (p != -1) {
		if (e[p].y != father) {
			dfs1(e[p].y, x);
			size[x] += size[e[p].y];
			if (!son[x] || size[son[x]] < size[e[p].y]) son[x] = e[p].y;
		}
		p = e[p].next;
	}
}
int timpoint = 0, id[50010];
void dfs2(int x, int parent) {
	id[x] = ++timpoint;
	price1[id[x]] = price[x];
	par[x] = parent;
	if (son[x]) dfs2(son[x], parent);
	int p = h[x];
	while (p != -1) {
		if (e[p].y != f[x] && e[p].y != son[x]) dfs2(e[p].y, e[p].y);
		p = e[p].next;
	}
}
int max(int a, int b) {return (a < b)? b: a;}
int min(int a, int b) {return (a < b)? a: b;}
struct point {
	int l, r;
	point * ls, * rs;
	int maxp, minp, rise, maxdp, maxdn;
	point (int l = 0, int r = 0): l(l), r(r), ls(0), rs(0), maxp(0), minp(0), maxdp(0), maxdn(0), rise(0) {}
	void update() {
		maxp = max(ls->maxp, rs->maxp) + rise;
		minp = min(ls->minp, rs->minp) + rise;
		maxdp = max(max(ls->maxdp, rs->maxdp), rs->maxp - ls->minp);
		maxdn = max(max(ls->maxdn, rs->maxdn), ls->maxp - rs->minp);
	}
	void push() {
		if (rise) {
			ls->rise += rise;
			rs->rise += rise;
			rise = 0;
		}
	}
} p[200010];
typedef point * link;
link root;
int ttp = 0;
link make(int l, int r) {
	int w = ++ttp;
	p[w] = point(l, r);
	if (l < r) {
		int mid = (l + r) >> 1;
		p[w].ls = make(l, mid);
		p[w].rs = make(mid+1, r);
		p[w].update();
	} else p[w].rise = p[w].maxp = p[w].minp = price1[l], p[w].maxdp = p[w].maxdn = 0;
	return &p[w];
}
const int ml = 2147480000;
struct result {
	int min, max, maxdn, maxdp;
	result(int min = ml, int max = 0, int maxdn = 0, int maxdp = 0): min(min), max(max), maxdn(maxdn), maxdp(maxdp) {}
};
result check(link p, int l, int r, int rise) {
	if (l <= p->l && p->r <= r) {
		p->rise += rise; 
		p->maxp += rise;
		p->minp += rise;
		return result(p->minp - rise, p->maxp - rise, p->maxdn, p->maxdp);
	}
	int mid = (p->l + p->r) >> 1;
	result r1, r2;
	if (l <= mid) r1 = check(p->ls, l, r, rise);
	if (mid < r) r2 = check(p->rs, l, r, rise);
	p->update();
	return result(min(r1.min, r2.min)+p->rise, max(r1.max, r2.max)+p->rise, max(r1.max - r2.min, max(r2.maxdn, r1.maxdn)), max(r2.max - r1.min, max(r2.maxdp, r1.maxdp)));
}
int jump(int x, int y, int z) {
	int fx = par[x], fy = par[y];
	int lmin = ml, rmax = 0, ans = 0;
	while (fx != fy) {
		if (dp[fx] > dp[fy]) {
			result r1 = check(root, id[fx], id[x], z);
			ans = max(ans, max(r1.maxdn, r1.max - lmin));
			lmin = min(lmin, r1.min);
			x = f[fx]; fx = par[x];
		} else {
			result r1 = check(root, id[fy], id[y], z);
			ans = max(ans, max(r1.maxdp, rmax - r1.min));
			rmax = max(rmax, r1.max);
			y = f[fy]; fy = par[y];
		}
	}
	if (dp[x] < dp[y]) {
		result r2 = check(root, id[x], id[y], z);
		ans = max(max(ans, max(rmax, r2.max) - lmin), max(rmax - min(lmin, r2.min), r2.maxdp));
	} else {
		result r2 = check(root, id[y], id[x], z);
		ans = max(max(ans, max(rmax, r2.max) - lmin), max(rmax - min(lmin, r2.min), r2.maxdn));
	}
	return ans;
}
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();
	memset(h, -1, sizeof(h));
	for (int i = 1; i < n; i++) {
		int x = read(), y = read();
		match(x, y);
	}
	head = 1;
	memset(dp, 0, sizeof(dp));
	dfs1(head, 0);
	dfs2(head, head);
	root = make(1, n);
	int m = read();
	for (int i = 1; i <= m; i++) {
		int st = read(), en = read(), rise = read();
		int ans = jump(st, en, rise);
		printf("%d\n", ans);
	}
	return 0;
}