| 记录编号 |
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;
}