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

发表于 | 分类于 |

做点简单 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
#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);
  }
}

Gitalking ...