LibreOJ 6699 然而第六章的 A 面并没有草莓

做点简单 DP 陶冶情操。

考虑按以下方式行动必然不劣：
对于路径上每个点，以其为根，首先穿到不在路径上的点的子树中移动（并且这些边最多往返各经过一次），然后回到路径上走到下一个点。

考虑求出每个点为根时在各个子树内移动的最小代价，查询时减掉路径上的相邻点的贡献即可。
记其为 fu。

不妨先计算 gu 为任选一根时不考虑 u 的当前根向子树的答案。那么有显然转移 gu=au+∑v∈child(u)max{0,gv−z(u,v)−z(v,u)}

对于 u 和 v∈child(u)，考虑按换根套路计算 fv，无非是 gv+max{0,fu−max{0,gv−z(u,v)−z(v,u)}−z(u,v)−z(v,u)}。

对于询问 (x,y)，先计算路径上的边权和，然后剩下的部分就是 flca(x,y)+∑u∈path(x,y)∖{lca(x,y)}(gu−max{0,gu−z(u,fa(u))−z(fa(u),u)})=flca(x,y)+∑u∈path(x,y)∖{lca(x,y)}min{gu,z(u,fa(u))+z(fa(u),u)}

代码：

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

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);
  }
}