\(\mathscr{Description}\)
给定一棵含有 \(n\) 个点的带点权树和大小为 \(m\) 的有序点对集合 \(\{(s_i,t_i)\}_{i=1}^n\). 每次操作可以选择一个 \(s_i\), 将其更改为其一个邻接点. 求让所有 \(s_i=t_i\) 的过程中, \(\sum_{i=1}^m w(s_i)\) 的最大值的最小值.
\(m\le n\le5\times10^3\).
\(\mathscr{Solution}\)
首先需要明确: 并不一定沿着最短路将 \(s_i\) 移动到 \(t_i\), 我们可以通过将一个点卡在它能走到的一个点权较小的结点处用于腾挪.
"能走到的点权最小的结点"? 那就对点权建一个大根 Kruskal 重构树叭. 每个结点能走到的点权最小的结点就是其子树最小值.
如何进行移动呢? 不妨记一开始的位置集合为 \(S_0\), 我们肯定先将每个点都移动向各自子树内点权最小的结点, 得到 \(S_0'\); 接下来再选择 \(S_0'\) 中的某个点 \(x\) 走到其在 \(S_0\) 中对应结点的父亲, 得到 \(S_1\). 设点 \(u\) 在 Kruskal 重构树上的子数最小值为 \(l(u)\), 那么在这一过程中, 点权和将在 \(\sum_{u\in S_1}w(u)\) 达到峰值, 这一值也就是 \(\sum_{u\in S_0}l(u)-l(x)+w(p_x)\).
当然, 这仅仅是移动的一般情况. 当务之急是确定如何选取这个 \(x\in S_0\). 不妨记目前答案为 \(\textit{ans}\), 那么我们有一个暴力做法: 不断令 \(\textit{ans}\gets\textit{ans}+1\) 直到恰好出现一个可以移动的 \(x\), 由于 \(x\) 上移不会让子树最小值变大, 因此此时移动 \(x\) 肯定是不劣. 我们只需要求出这个时候的 \(\textit{ans}\) 及其对应的 \(x\) 就能完成迭代了. 很显然, 此时 \(\textit{ans}\ge\sum_{u\in S_0}l(u)+\min\{\Delta_x\}\) (可能 \(\Delta_x<0\)), 所以直接取 \(\arg\min\{\Delta_x\}\) 就是最有的决策.
现在, 我们完成了 "从 \(S\) 向上爬" 的策略, 不过这并不能指导我们如何走到 \(T\). 这里有一个思维 trick: 因为移动过程是可逆的, 所以我们不妨让 \(T\) 向上爬. 当目前的 \(\textit{ans}\) 合法时, 有一个必要条件: \(S\) 能爬到的最高点对应 \(T\) 能爬到的最高点.
问题是, 在我们的策略中, 当一个 \(s_i\) 爬到最高点, 其余所有 \(s\) 都是呆在某个子树最小值位置的, 如何拼接从 \(S\) 出发的方案和从 \(T\) 出发的方案呢? 其实很简单, 当 \(S\) 能爬到的最高点对应 \(T\) 能爬到的最高点时, 我们先让所有 \(S\) 走到自己最高点所对应的子树最小值位置 --- 挨个移动, 一定可行. 此后, 将这些最小值位置调整到各自在 \(T\) 中的最小值位置 --- 这些最小值一一相等, 完全不会影响方案可行性. 最后, 我们已经完全移动把结点丢到 \(T\) 的方案内了, 回溯到重点即可.
直接用堆模拟贪心过程, 可以做到 \(\mathcal O(nm\log m)\).
\(\mathscr{Code}\)
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
typedef long long LL;
typedef std::pair<int, int> PII;
#define fi first
#define se second
const int MAXN = 5e3;
int n, m, val[MAXN + 5], ord[MAXN + 5];
std::vector<int> G[MAXN + 5], T[MAXN + 5];
struct DSU {
int fa[MAXN + 5];
inline void init() {
rep (i, 1, n) fa[i] = i;
}
inline int find(const int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
} dsu;
int fa[MAXN + 5], mn[MAXN + 5], cur[MAXN + 5][2];
inline void init(const int u) {
mn[u] = val[u];
for (int v: T[u]) fa[v] = u, init(v), mn[u] = std::min(mn[u], mn[v]);
}
int main() {
scanf("%d", &n);
rep (i, 1, n) scanf("%d", &val[i]);
rep (i, 2, n) {
int u, v; scanf("%d %d", &u, &v);
G[u].push_back(v), G[v].push_back(u);
}
std::iota(ord + 1, ord + n + 1, 1);
std::sort(ord + 1, ord + n + 1,
[](const int u, const int v) {
return val[u] < val[v];
}
);
dsu.init();
rep (i, 1, n) {
int u = ord[i];
for (int v: G[u]) if (val[v] < val[u] + (v < u)) {
// printf("%d %d\n", u, dsu.find(v));
T[u].push_back(dsu.find(v)), dsu.fa[dsu.find(v)] = u;
}
}
init(ord[n]);
scanf("%d", &m);
int rest = 0;
LL s0 = 0, t0 = 0, sum[2] = {};
std::priority_queue<PII, std::vector<PII>, std::greater<PII>> heap;
rep (i, 1, m) {
int s, t;
scanf("%d %d", &s, &t);
cur[i][0] = s, cur[i][1] = t;
rest += s != t, s0 += val[s], t0 += val[t];
sum[0] += mn[s], sum[1] += mn[t];
// printf("%d %d %d\n", s, t, tar[i]);
if (fa[s]) heap.emplace(val[fa[s]] - mn[s], i);
if (fa[t]) heap.emplace(val[fa[t]] - mn[t], -i);
}
LL ans = std::max(s0, t0);
while (rest) {
PII p = heap.top(); heap.pop();
int tp = p.se < 0, id = tp ? -p.se : p.se;
ans = std::max(ans, sum[tp] + p.fi);
rest += cur[id][0] == cur[id][1], sum[tp] -= mn[cur[id][tp]];
cur[id][tp] = fa[cur[id][tp]];
rest -= cur[id][0] == cur[id][1], sum[tp] += mn[cur[id][tp]];
if (fa[cur[id][tp]]) {
heap.emplace(val[fa[cur[id][tp]]] - mn[cur[id][tp]], p.se);
}
}
printf("%lld\n", ans);
return 0;
}