Algorithm - Problem - [上海赛前集训] 买卖收益

[上海赛前集训] 买卖收益

问题描述

一个国家有 NN 个城市,由 N1N-1 条双向道路连接,任意两个城市间都有唯一的路径。

某一种商品,在第 ii 个城市的价格为 AiA_i 。小明如果从一个城市到另一个城市,一共只会在路径上交易两次,一次是买入,一次是卖出。

现在有 QQ 次询问,每次告诉你两个城市,请问从城市 xx 到城市 yy,或者从城市 yy 到城市 xx 能获得的最大收益是多少?

输入

输入文件 profit.in

第一行,包含两个整数 N,QN,Q

第二行,包含 NN 个整数 A1,A2,,AnA_1,A_2,\cdots,A_n

后续 N1N-1 行,每行两个整数 x,yx,y,表示城市 xx 到城市 yy 之间有一条双向道路。

后续 QQ 行,每行两个整数 x,yx,y

输出

输出文件 profit.out

QQ 行,每行包含一个整数,表示最大利润

样例输入
1
2
3
4
5
6
7
8
9
5 3
1 2 3 4 5
1 2
1 3
3 4
3 5
1 5
3 5
4 5
样例输出
1
2
3
4
2
2
提示

30%30\% 的数据,Q1000Q\leqslant 1000, N1000N\leqslant 1000

另外 30%30\% 的数据,N−1 条道路分别在城市 i+1i+1 和城市 i(1iN)i(1\leqslant i\leqslant N) 之间

100%100\% 的数据,2N1052\leqslant N\leqslant 10^5, 1Q1051\leqslant Q\leqslant 10^5, 1Ai1091\leqslant A_i\leqslant 10^9, xyx\neq y

树上倍增

分析

显然,本题建得的图是一棵树.
令数组 f[i][j]f[i][j] 表示城市 ii 的第 2j2^j 个父亲城市.
令数组 max[i][j]max[i][j] 表示从城市 ii 到城市 f[i][j]f[i][j] 所经过城市中价格的最大值,不难发现有

max[i][j]=max(max[i][j1],max[f[i][j1]][j1]).max[i][j] = \max(max[i][j - 1], max[f[i][j - 1]][j - 1]).

类似地,对 minmin 数组同理. 因此,不难想到对应的树上倍增 LCA 与 RMQ.

代码

这份代码可以说写的很脏了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (100000+5)
#define INFTY (0x7FFFFFFF)
#define MAXDEPTH (20)
#define MIN(a,b) (((a)<(b))?(a):(b))
#define MAX(a,b) (((a)>(b))?(a):(b))
int ecnt = 0;
int ex[2 * MAXN];
int ey[2 * MAXN];
int head[MAXN];
int next[2 * MAXN];
int price[MAXN];
int depth[MAXN], f[MAXN][MAXDEPTH + 1], max[MAXN][MAXDEPTH + 1], min[MAXN][MAXDEPTH + 1];
int n, q, x, y;
void add(int x, int y)
{
ex[ecnt] = x;
ey[ecnt] = y;
next[ecnt] = head[x];
head[x] = ecnt++;
}
bool dfs(int u, int v) // v->u->ey[a];
{
int a = head[u];
depth[u] = depth[v] + 1;
f[u][0] = v;
for(int i = 1; i <= MAXDEPTH; i++)
{
if(f[u][i - 1])
{
min[u][i] = MIN(min[u][i - 1], min[f[u][i - 1]][i - 1]);
max[u][i] = MAX(max[u][i - 1], max[f[u][i - 1]][i - 1]);
f[u][i] = f[f[u][i - 1]][i - 1];
}
else
{
break;
}
}
while(a != -1)
{
if(ey[a] == v)
{
a = next[a];
continue;
}
min[ey[a]][0] = MIN(price[ey[a]], price[u]);
max[ey[a]][0] = MAX(price[ey[a]], price[u]);
dfs(ey[a], u);
a = next[a];
}
}
int rmq(int u, int v)
{
int delta;
int max_ans = 0, min_ans = INFTY;
if(depth[u] > depth[v])
{
int t = u; u = v; v = t;
}
delta = depth[v] - depth[u];
for(int i = 0; i <= MAXDEPTH; i++)
{
if(delta & (1 << i))
{
max_ans = MAX(max_ans, max[v][i]);
min_ans = MIN(min_ans, min[v][i]);
v = f[v][i];
}
}
if(u == v) return (max_ans - min_ans);
for(int i = MAXDEPTH; i >= 0 && (u != v); i--)
{
if(f[u][i] != f[v][i])
{
max_ans = MAX(max_ans, MAX(max[u][i], max[v][i]));
min_ans = MIN(min_ans, MIN(min[u][i], min[v][i]));
u = f[u][i];
v = f[v][i];
}
}
max_ans = MAX(max_ans, MAX(max[u][0], max[v][0]));
min_ans = MIN(min_ans, MIN(min[u][0], min[v][0]));
return (max_ans - min_ans);
}
int main()
{
freopen("profit.in", "r", stdin);
freopen("profit.out", "w", stdout);
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++)
{
head[i] = -1;
scanf("%d", &price[i]);
min[i][0] = INFTY;
}
for(int i = 0; i < MAXN; i++)
{
next[i] = -1;
}
for(int i = 0; i < n - 1; i++)
{
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
for(int i = 0; i < q; i++)
{
scanf("%d%d", &x, &y);
printf("%d\n", rmq(x, y));
}
fclose(stdin);
fclose(stdout);
}