题解：P17724 [SCP-S 2026] 路短最 / path
time_keeper
·
·
题解
手摸一下一个 k 元环的样例，假设这个环是 r = v_0, v_1, \cdots v_{k - 1}, v_k = r。可以选择方向使得 v_1 < v_{k - 1}。更新方式是先顺着走一遍，然后再从 v_{k - 1} \to v_{\frac{k}{2}} 走过来。
如果把更新距离刻画为一个 $h = d_u' - d_u$ 减少的过程。在这样一个 $k$ 元环的 $r$ 上减少 $h$。考虑环上到 $r$ 的距离 $\min(i, k - i)$。能被更新两次的点是 $k - i < i$ 且 $2i - k < h$，记 $e_i = 2i - k$ 的话即 $0 < e_i < h$。后者这个要求是可能顺着更新到 $i$ 时不如原来优，即 $d+k-i+h<d+i$。
特殊的，$v_{k - 1}$ 的 $e_i = 0$，因为其在 $r$ 处就被更新了。
对于两次更新的点，两次分别会减少 $h - e_i$ 和 $e_i$。前者是顺着更新，后者是逆着更新的。
我们把环上的 $v_1 \cdots v_{k - 1}$ 挂在 $r$ 下面，边权是 $e_i$。设 $f_{u, i}$ 表示 $u$ 考虑子树内的点，如果 $d_u$ 下降 $i$，$C$ 会增加多少。转移考虑 边权 $w$ 和 $h$ 的关系。
$$f_{u, i} = \begin{cases}
f_{v, i} & i \le w\\
f_{v, w} + f_{v, i - w} & i > w
\end{cases}$$
直接 DP 是 $O(n^2)$ 的。考虑 $f_{u, i}$ 的差分数组 $g_{u, i} = f_{u, i} - f_{u, i - 1}$，则转移可以写为：
$$g_{u, i} = \begin{cases}
g_{v, i} & i \le w\\
g_{v, i - w} & i > w
\end{cases}$$
$$f_{u, i} = \sum_{v \in son(u)} g_{v, i} + 1$$
相当于把 $g_{v, 0 \sim w}$ 复制向前接了一段。
而且考察 $g_{u, i}$ 非 $0$ 位置个数，对于叶子结点是 $1$。对于非叶子结点，其有值位置的范围 $siz_u = \max_v (siz_v + w_v)$。记最大的那个为重儿子。
对于一条重链，$\sum siz_u = \sum_{v \in subtree(u)} [leaf(v)] + \sum w_u$。
每个环只能选一个重儿子，所以每个大小为 $k$ 的环至多贡献一个 $w_i \le k$。那么总和是 $O(n)$ 的。
这个过程直接拿可持久化平衡树维护一下就是 $O(n \log n)$ 的。赛时写的可持久化 wblt。
:::success[code]
```cpp
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
using ll = long long;
constexpr int MaxN = 5e5 + 10;
constexpr int MaxM = 7.5e5 + 10;
bool Mbe;
int n, m;
struct edge {
int u, v;
} e[MaxM * 2];
int h[MaxN], tot = 0;
inline void add_edge(int u, int v) {
e[++tot] = {h[u], v}; h[u] = tot;
e[++tot] = {h[v], u}; h[v] = tot;
}
vector<pair<int, int>> G[MaxN];
inline void link(int u, int v, int w) {
G[u].emplace_back(v, w);
}
int dfn[MaxN], fa[MaxN], sta[MaxN], vis[MaxN], tim = 0, top = 0;
void pdfs(int u, int par) {
sta[++top] = u;
dfn[u] = ++tim;
vis[u] = true;
for (int i = h[u]; i; i = e[i].u) {
int v = e[i].v;
if (v == par) continue;
if (!dfn[v]) {
pdfs(v, u);
} else if (vis[v] && dfn[v] < dfn[u]) {
int r = v;
int pos = top;
while (pos && sta[pos] != r) --pos;
int L = top - pos + 1;
int p1 = sta[pos + 1], pk = sta[top];
vector<int> seq;
seq.reserve(L);
if (p1 < pk) {
for (int j = pos; j <= top; j++)
seq.emplace_back(sta[j]);
} else {
seq.emplace_back(r);
for (int j = top; j > pos; --j)
seq.emplace_back(sta[j]);
}
for (int i = 1; i < L; i++) {
int x = seq[i], w = 0;
if (i != L - 1) w = max(0, 2 * i - L);
link(r, x, w);
fa[x] = r;
}
}
}
if (!fa[u]) {
fa[u] = par;
if (par) link(par, u, 0);
}
vis[u] = false;
top--;
}
constexpr int MaxS = 1.5e7;
struct Node {
int ch[2];
int siz, mx, mn, tag;
ll sum;
void print() {
debug("(%d, %d, %lld), ", mx, tag, sum);
}
} tr[MaxS];
int idx = 0;
#define ch(x, y) (tr[x].ch[y])
#define siz(x) (tr[x].siz)
#define mx(x) (tr[x].mx)
#define mn(x) (tr[x].mn)
#define tag(x) (tr[x].tag)
#define sum(x) (tr[x].sum)
int create(int v, ll w) {
tr[++idx] = {{0, 0}, 1, v, v, 0, w};
return idx;
}
int refresh(int x) {
int y = ++ idx;
tr[y] = tr[x];
return y;
}
void push_up(int x) {
siz(x) = siz(ch(x, 0)) + siz(ch(x, 1));
mx(x) = mx(ch(x, 1));
mn(x) = mn(ch(x, 0));
sum(x) = sum(ch(x, 0)) + sum(ch(x, 1));
}
int apply(int x, ll w) {
if (!x || !w) return x;
int y = refresh(x);
mx(y) += w, mn(y) += w, tag(y) += w;
return y;
}
void push_down(int x) {
if (!tag(x) || siz(x) == 1) return;
int w = tag(x);
ch(x, 0) = apply(ch(x, 0), w);
ch(x, 1) = apply(ch(x, 1), w);
tag(x) = 0;
}
int merge(int x, int y) {
if (!x || !y) return x | y;
int S = siz(x) + siz(y);
if (min(siz(x), siz(y)) * 4 >= S) {
int z = create(0, 0);
ch(z, 0) = x, ch(z, 1) = y;
return push_up(z), z;
}
if (siz(x) >= siz(y)) {
push_down(x);
if (siz(ch(x, 0)) * 4 >= S)
return merge(ch(x, 0), merge(ch(x, 1), y));
int z = ch(x, 1);
push_down(z);
return merge(merge(ch(x, 0), ch(z, 0)), merge(ch(z, 1), y));
} else {
push_down(y);
if (siz(ch(y, 1)) * 4 >= S)
return merge(merge(x, ch(y, 0)), ch(y, 1));
int z = ch(y, 0);
push_down(z);
return merge(merge(x, ch(z, 0)), merge(ch(z, 1), ch(y, 1)));
}
}
void split(int x, int k, int &p, int &q) {
if (!x) return p = q = 0, void();
if (mx(x) <= k) return p = x, q = 0, void();
if (mn(x) > k) return p = 0, q = x, void();
push_down(x);
if (mx(ch(x, 0)) >= k) {
split(ch(x, 0), k, p, q);
q = merge(q, ch(x, 1));
} else {
split(ch(x, 1), k, p, q);
p = merge(ch(x, 0), p);
}
}
int merge1(int x, int y) {
if (!x || !y) return x | y;
if (mx(x) < mn(y)) return merge(x, y);
if (mx(y) < mn(x)) return merge(y, x);
if (siz(x) > siz(y)) swap(x, y);
if (siz(x) == 1) {
int a, b, c, d;
split(y, mx(x) - 1, a, b);
split(b, mx(x), c, d);
c = create(mx(x), sum(x) + sum(c));
return merge(merge(a, c), d);
}
push_down(x);
int a, b;
split(y, mx(ch(x, 0)), a, b);
return merge(merge1(ch(x, 0), a), merge1(ch(x, 1), b));
}
void print(int x) {
if (!x) return;
if (!ch(x, 0)) {
tr[x].print();
} else {
push_down(x);
print(ch(x, 0)), print(ch(x, 1));
}
}
int siz[MaxN], rt[MaxN];
void dfs(int u) {
siz[u] = 1;
rt[u] = create(1, 1);
for (auto [v, w] : G[u]) {
dfs(v);
siz[u] += siz[v];
int x = rt[v];
if (w) {
int a, b;
split(x, w, a, b);
x = merge(a, apply(x, w));
}
rt[u] = merge1(rt[u], x);
}
// debug("T[%d] = ", u);
// print(rt[u]);
// debug("\n");
}
void solve() {
cin >> n >> m;
tot = tim = top = idx = 0;
for (int i = 1; i <= n; i++) {
G[i].clear();
h[i] = dfn[i] = fa[i] = vis[i] = 0;
}
for (int i = 1, u, v; i <= m; i++) {
cin >> u >> v;
add_edge(u, v);
}
pdfs(1, 0);
dfs(1);
cout << sum(rt[1]) << '\n';
}
bool Men;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
debug(" used %.4lf\n", (&Mbe - &Men) / 1024.0 / 1024.0);
int cid, T;
cin >> cid >> T;
while (T--) solve();
}
```
:::
你发现这个过程很像长剖。每个节点开 $2 \times siz_u$ 的数组。先继承重儿子的 dp 值到 $f[u][w \sim siz]$ 然后做合并。最后把 $f[u][0 \sim w]$ 的值复制上即可。这样合并的复杂度是 $O(\sum siz_v)$ 的。
所有轻儿子恰好对应除了跟以外的重链链头，每条重链都 $\le 2siz$。故这样做复杂度是 $O(n + m)$ 的。