题意：给出N个点，和每个点物品的售价，现在有一个商人，要从u点到v点，他想在路上多赚点钱。他可以从一个城市买物品，然后再卖到另一个城市，但买卖只允许一次，且不能回头走，问最多能赚多少。
题解：在线查询+倍增lca n个点的生成树，路径有且只有一条，所以考虑lca路径。
接下来考虑如何获取利润的最大值。 从u到v，差值只可能出现在u到lca、u到v、lca到v这三种路径上。
对于u到lca路径，用up数组记录最大利润。 对于lca到v路径，用down数组记录最大路径。 对于u到v路径，需要记录左路径的最小值Min，以及右路径的最大值Max。
更新的时候用倍增即可，查询时也是常数的复杂度。
注意更新up和down时可能会出现负值，跟0比较一下。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<queue> #include<stack> #include<cmath> #include<vector> #include<fstream> #include<set> #include<map> #include<sstream> #include<iomanip> #define ll long long #define pii pair<int, int> using namespace std; const int MAXN = 5e4 + 5; int n, q; vector<int> v[MAXN]; int fa[MAXN][31], dep[MAXN]; int Max[MAXN][31], Min[MAXN][31], up[MAXN][31], down[MAXN][31]; int a[MAXN]; void dfs(int root, int fno) { //1 0 fa[root][0] = fno; dep[root] = dep[fa[root][0]] + 1; for (int i = 1; i < 31; ++i) { fa[root][i] = fa[fa[root][i - 1]][i - 1]; Max[root][i] = max(Max[root][i - 1], Max[fa[root][i - 1]][i - 1]); Min[root][i] = min(Min[root][i - 1], Min[fa[root][i - 1]][i - 1]); up[root][i] = max(up[root][i - 1], up[fa[root][i - 1]][i - 1]); up[root][i] = max(up[root][i], max(0, Max[fa[root][i - 1]][i - 1] - Min[root][i - 1])); down[root][i] = max(down[root][i - 1], down[fa[root][i - 1]][i - 1]); down[root][i] = max(down[root][i], max(0, Max[root][i - 1] - Min[fa[root][i - 1]][i - 1])); } int sz = v[root].size(); for (int i = 0; i < sz; ++i) { int vv = v[root][i]; if (vv == fno) continue; Max[vv][0] = max(a[root], a[vv]); Min[vv][0] = min(a[root], a[vv]); up[vv][0] = max(0, a[root] - a[vv]); down[vv][0] = max(0, a[vv] - a[root]); dfs(v[root][i], root); } } int lca(int x, int y) { if (dep[x] > dep[y]) swap(x, y); int tmp = dep[y] - dep[x]; for (int j = 0; tmp; ++j, tmp >>= 1) if (tmp & 1) y = fa[y][j]; if (y == x) return x; for (int j = 30; j >= 0 && y != x; --j) { if (fa[x][j] != fa[y][j]) { x = fa[x][j]; y = fa[y][j]; } } return fa[x][0]; } int minv, maxv; int qup(int u, int d) { minv = 0x3f3f3f3f; int ans = 0; for (int i = 0; d; i++, d >>= 1) { if (d & 1) { ans = max(ans, up[u][i]); ans = max(ans, Max[u][i] - minv); //注意minv minv = min(minv, Min[u][i]); u = fa[u][i]; } } return ans; } int qdown(int u, int d) { maxv = 0; int ans = 0; for (int i = 0; d; i++, d >>= 1) { if (d & 1) { ans = max(ans, down[u][i]); ans = max(ans, maxv - Min[u][i]); maxv = max(maxv, Max[u][i]); u = fa[u][i]; } } return ans; } int main() { int x, y; scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i < n; i++) { scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); } dfs(1, 0); scanf("%d", &q); while (q--) { scanf("%d%d", &x, &y); int lc = lca(x, y); int a = qup(x, dep[x] - dep[lc]); int b = qdown(y, dep[y] - dep[lc]); int ans = max(a, b); ans = max(ans, maxv - minv); printf("%d\n", ans); } return 0; }