做点简单 DP 陶冶情操。
考虑按以下方式行动必然不劣：
对于路径上每个点，以其为根，首先穿到不在路径上的点的子树中移动（并且这些边最多往返各经过一次），然后回到路径上走到下一个点。
考虑求出每个点为根时在各个子树内移动的最小代价，查询时减掉路径上的相邻点的贡献即可。
记其为 \(f_u\)。
不妨先计算 \(g_u\) 为任选一根时不考虑 \(u\) 的当前根向子树的答案。那么有显然转移 \[ \newcommand\fa{ \operatorname{fa} } \newcommand\lca{ \operatorname{lca} } \newcommand\child{ \operatorname{child} } \newcommand\path{ \operatorname{path} } g_u = a_u + \sum_{v\in\child(u)} \max\{0,g_v - z(u,v) - z(v,u)\} \]
对于 \(u\) 和 \(v\in\child(u)\)，考虑按换根套路计算 \(f_v\)，无非是 \(g_v+\max\{0, f_u-\max\{0,g_v-z(u,v)-z(v,u)\}-z(u,v)-z(v,u)\}\)。
对于询问 \((x,y)\)，先计算路径上的边权和，然后剩下的部分就是 \[ \begin{aligned} &\quad\;f_{\lca(x,y)} + \sum_{ u\in\path(x,y)\setminus\{\lca(x,y)\} } (g_u-\max\{0,g_u-z(u,\fa(u))-z(\fa(u),u)\}) \\ &=f_{\lca(x,y)} + \sum_{ u\in\path(x,y)\setminus\{\lca(x,y)\} } \min\{g_u,z(u,\fa(u))+z(\fa(u),u)\} \end{aligned} \]
代码： 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
using ll = long long;
using namespace std;
const int N = 2e5;
const int LG = 17;
int n, q;
vector<pair<int, int>> e[N + 5];
int a[N + 5], w[2][N + 5];
int fa[N + 5], dep[N + 5], faBinary[LG + 5][N + 5];
ll f[N + 5], g[N + 5], wSum[2][N + 5];
ll sum[N + 5];
void dfs1(int u) {
g[u] = a[u], wSum[0][u] = wSum[0][fa[u]] + w[0][u];
faBinary[0][u] = fa[u];
for (int i = 1; i <= LG; ++i)
faBinary[i][u] = faBinary[i - 1][faBinary[i - 1][u]];
for (auto one: e[u]) {
int v = one.first, z = one.second;
if (v != fa[u])
fa[v] = u, dep[v] = dep[u] + 1, w[0][v] = z, dfs1(v), g[u] += max(0LL, g[v] - w[0][v] - w[1][v]);
else
w[1][u] = z;
}
}
void dfs2(int u) {
wSum[1][u] = wSum[1][fa[u]] + w[1][u];
sum[u] = sum[fa[u]] + min(g[u], (ll)w[0][u] + w[1][u]);
for (auto one: e[u]) {
int v = one.first;
if (v != fa[u])
f[v] = g[v] + max(0LL, f[u] - max(0LL, g[v] - w[0][v] - w[1][v]) - w[0][v] - w[1][v]), dfs2(v);
}
}
inline int lca(int x, int y) {
if (dep[x] < dep[y])
swap(x, y);
for (int i = LG; i >= 0; --i)
if (faBinary[i][x] && dep[faBinary[i][x]] >= dep[y])
x = faBinary[i][x];
if (x == y)
return x;
for (int i = LG; i >= 0; --i)
if (faBinary[i][x] != faBinary[i][y])
x = faBinary[i][x], y = faBinary[i][y];
return fa[x];
}
ll ans;
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i)
scanf("%d", a + i);
for (int i = 2; i <= n; ++i) {
int u, v, w0, w1;
scanf("%d%d%d%d", &u, &v, &w0, &w1);
e[u].emplace_back(v, w0), e[v].emplace_back(u, w1);
}
dfs1(1), f[1] = g[1], dfs2(1);
for (int x, y; q; --q) {
scanf("%d%d", &x, &y);
int anc = lca(x, y);
ans = f[anc];
ans += sum[x] + sum[y] - 2 * sum[anc];
ans -= wSum[1][x] + wSum[0][y] - wSum[0][anc] - wSum[1][anc];
printf("%lld\n", ans);
}
}