| 记录编号 |
162975 |
评测结果 |
AAAAAAAAA |
| 题目名称 |
[TJOI 2015] 旅游 |
最终得分 |
100 |
| 用户昵称 |
 RP++ |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
1.960 s |
| 提交时间 |
2015-05-22 11:28:49 |
内存使用 |
7.91 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
#define maxn 50010
#define INF 0x3fffffff
#define lson root<<1, l, mid
#define rson root<<1|1, mid + 1, r
int n, tot, dfs_clock, res, mmax, mmin;
int to[maxn<<1], next[maxn<<1], head[maxn];
int num[maxn], top[maxn], deep[maxn], son[maxn], size[maxn], fa[maxn], pre[maxn], pos[maxn];
int Max1[maxn<<2], Min1[maxn<<2], ans1[maxn<<2], add1[maxn<<2], Max[maxn<<2], Min[maxn<<2], ans[maxn<<2], add[maxn<<2];
inline void Build(int s, int t) {
to[++tot] = t, next[tot] = head[s], head[s] = tot;
}
inline void dfs_1(int u) {
size[u] = 1;
for(int i = head[u]; i; i = next[i]) {
int l = to[i];
if(!size[l]) {
deep[l] = deep[u] + 1; dfs_1(l);
size[u] += size[l], fa[l] = u;
if(size[l] > size[son[u]]) son[u] = l;
}
}
}
inline void dfs_2(int u, int t) {
pre[++dfs_clock] = num[u], pos[u] = dfs_clock, top[u] = t;
if(son[u]) dfs_2(son[u], t);
for(int i = head[u]; i; i = next[i]) {
int l = to[i];
if(l != fa[u] && l != son[u]) dfs_2(l, l);
}
}
inline void Buildtree(int root, int l, int r) {
if(l == r) {
Max[root] = Min[root] = pre[l], Max1[root] = Min1[root] = pre[n + 1 - l];
return ;
}
int mid = (l + r) >> 1;
Buildtree(lson), Buildtree(rson);
Max[root] = max(Max[root<<1], Max[root<<1|1]), Min[root] = min(Min[root<<1], Min[root<<1|1]);
ans[root] = max(max(ans[root<<1], ans[root<<1|1]), Max[root<<1|1] - Min[root<<1]);
Max1[root] = max(Max1[root<<1], Max1[root<<1|1]), Min1[root] = min(Min1[root<<1], Min1[root<<1|1]);
ans1[root] = max(max(ans1[root<<1], ans1[root<<1|1]), Max1[root<<1|1] - Min1[root<<1]);
}
inline void Pushup(int x) {
Max[x] = max(Max[x<<1], Max[x<<1|1]), Min[x] = min(Min[x<<1], Min[x<<1|1]);
ans[x] = max(max(ans[x<<1], ans[x<<1|1]), Max[x<<1|1] - Min[x<<1]);
}
inline void Pushdown(int x) {
Max[x<<1] += add[x], Min[x<<1] += add[x], add[x<<1] += add[x];
Max[x<<1|1] += add[x], Min[x<<1|1] += add[x], add[x<<1|1] += add[x];
add[x] = 0;
}
inline void modify(int root, int l, int r, int s, int t, int x) {
if(l < r && add[root]) Pushdown(root);
if(s <= l && t >= r) {
Max[root] += x, Min[root] += x, add[root] += x;
return ;
}
int mid = (l + r) >> 1;
if(s <= mid) modify(lson, s, t, x);
if(t > mid) modify(rson, s, t, x);
Pushup(root);
}
inline void Pushdown1(int x) {
Max1[x<<1] += add1[x], Min1[x<<1] += add1[x], add1[x<<1] += add1[x];
Max1[x<<1|1] += add1[x], Min1[x<<1|1] += add1[x], add1[x<<1|1] += add1[x];
add1[x] = 0;
}
inline void Pushup1(int x) {
Max1[x] = max(Max1[x<<1], Max1[x<<1|1]), Min1[x] = min(Min1[x<<1], Min1[x<<1|1]);
ans1[x] = max(max(ans1[x<<1], ans1[x<<1|1]), Max1[x<<1|1] - Min1[x<<1]);
}
inline void modify1(int root, int l, int r, int s, int t, int x) {
if(l < r && add1[root]) Pushdown1(root);
if(s <= l && t >= r) {
Max1[root] +=x, Min1[root] += x, add1[root] += x;
return ;
}
int mid = (l + r) >> 1;
if(s <= mid) modify1(lson, s, t, x);
if(t > mid) modify1(rson, s, t, x);
Pushup1(root);
}
inline void query_tree(int root, int l, int r, int s, int t) {
if(l < r && add[root]) Pushdown(root);
if(s <= l && t >= r) {
res = max(max(res, ans[root]), Max[root] - mmin);
mmax = max(mmax, Max[root]), mmin = min(mmin, Min[root]);
return ;
}
int mid = (l + r) >> 1;
if(s <= mid) query_tree(lson, s, t);
if(t > mid) query_tree(rson, s, t);
}
inline void query_tree1(int root, int l, int r, int s, int t) {
if(l < r && add1[root]) Pushdown1(root);
if(s <= l && t >= r) {
res = max(max(res, ans1[root]), Max1[root] - mmin);
mmax = max(mmax, Max1[root]), mmin = min(mmin, Min1[root]);
return ;
}
int mid = (l + r) >> 1;
if(s <= mid) query_tree1(lson, s, t);
if(t > mid) query_tree1(rson, s, t);
}
inline int query(int x, int y, int k) {
int r1 = top[x], r2 = top[y], p = 0, mn = INF, mx = 0, l, r;
while(r1 != r2) {
if(deep[r1] > deep[r2]) {
l = n + 1 - pos[x], r = n + 1 - pos[r1], mmin = INF, mmax = 0, res = 0;
query_tree1(1, 1, n, l, r), modify1(1, 1, n, l, r, k), modify(1, 1, n, pos[r1], pos[x], k);
p = max(max(p, res), max(mx - mmin, mmax - mn)), mn = min(mn, mmin);
x = fa[r1], r1 = top[x];
} else {
l = pos[r2], r = pos[y], mmin = INF, mmax = 0, res = 0;
query_tree(1, 1, n, l, r), modify(1, 1, n, l, r, k), modify1(1, 1, n, n + 1 - pos[y], n + 1 - pos[r2], k);
p = max(max(p, res), max(mx - mmin, mmax - mn)), mx = max(mx, mmax);
y = fa[r2], r2 = top[y];
}
}
mmin = INF, mmax = 0, res = 0;
if(deep[x] < deep[y]) {
l = pos[x], r = pos[y], query_tree(1, 1, n, l, r);
modify(1, 1, n, l, r, k), modify1(1, 1, n, n + 1 - r, n + 1 - l, k);
} else {
l = n + 1 - pos[x], r = n + 1 - pos[y], query_tree1(1, 1, n, l, r);
modify1(1, 1, n, l, r, k), modify(1, 1, n, pos[y], pos[x], k);
}
return max(max(p, res), max(mx - mmin, mmax - mn));
}
int main() {
freopen("tjoi2015_travel.in", "r", stdin);
freopen("tjoi2015_travel.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &num[i]);
for(int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
Build(x, y), Build(y, x);
}
deep[1] = 1, dfs_1(1);
dfs_2(1, 1);
Buildtree(1, 1, n);
int m;
scanf("%d", &m);
for(int i = 1, k, x, y; i <= m; i++) {
scanf("%d%d%d", &x, &y, &k);
printf("%d\n", query(x, y, k));
}
}