8.5 KiB
P17437 「LWLV Round 1」Young 题解
根本没有这样的青题……题解区都看不懂……
题意：给定一棵节点带权值的树，断掉两条边，得到三个树，求三个树权值中位数最大是多少。
这里我们令 1 为根，边 id 表示连接 id 与其父节点的边，sum_i 表示以 i 为根的子树权值和。
枚举第一刀
先枚举第一条断边 $u$，会将树分为 u 的子树和剩下部分 $A, B$，第二刀只能落在 A 或 B 内部。问题变成：固定第一刀后，在某一侧内部再切一刀，使三块中位数最大。
命题：对于全局最优的两条切边，总存在其中一条边作为第一刀，使得最优三块的中位数可以由 dmin/dmax 或 umin/umax 四类候选之一达到。
::::error[错误命题]
先反驳一下一个结论：第二刀切出的一定是 A 或 B 的最大或最小子树。
带入数据：
6
0 1 3 2 3 1
1 2
2 3
3 4
4 5
5 6
发现第一刀切 1, 2 时，$dmax=9, dmin=1$。但是实际上这种情况下最优解为 a = 4 时，median = 4
但是按照这个命题实现的答案却是正确的，原因就是本命题
::::
::::success[证明] 设全局最优中位数为 $y$。任何切法的中位数都不可能超过 $y$，所以只要证明：总有一种候选切法能使中位数达到 $y$。
分两类看最优切法。
两个切点互不为祖先。
三块是两棵互不相交的子树和剩下的补集。若中位块是某棵子树，就把这棵子树作为第一刀，另一侧用最小或最大可切值切出另一棵子树，使另外两块分别落在 y 的两边，中位数仍是 $y$。若中位块是补集，就取权值不小于 y 的那棵子树作第一刀，再在另一侧切出剩下的子树，同样能让中位数达到 $y$。
两个切点有祖先关系。
三块是祖先外侧、中间夹层、后代子树。若中位块是后代，就取后代边作第一刀，在另一侧切出祖先外侧，用最小或最大可切值把中间夹层推到 y 的另一边。若中位块是祖先外侧，就取祖先边作第一刀，在子树侧切出后代，同理。若中位块是中间夹层，则外侧和后代一个不大于 $y$、一个不小于 $y$，此时无论取祖先边还是后代边作第一刀，再在另一侧取合适的极值，都能让三块中至少两块不小于 $y$、至少两块不大于 $y$，中位数仍为 $y$。
所以，全局最优中位数一定能在“枚举第一刀，另一侧取 dmin/dmax 或 $umin/umax$”这四类候选中出现。最终枚举第一刀并检查四类候选即可。
::::
预处理子树最大、最小可切值
若第二刀在 A 内部，则需要用到子树的最大、最小可切值。
记录 dmax_i, dmin_i 表示以 i 为根的子树的能切出的最大/最小权值子树，则结果为以一个儿子节点为根的子树的权值和或者以一个儿子节点为根的子树能切出的最大/最小权值子树。
\begin{aligned}
dmax_i =& \max(\max(s_u, dmax_u), u \in child_i) \\
dmin_i =& \min(\min(s_u, dmin_u), u \in child_i)
\end{aligned}
预处理“补集方向”最小、最大可切值
若第二刀切在 A 的补集 B 的方向，则需要“补集方向”的最小、最大可切值。
令 umax_i, umin_i 为补集方向的最大最小可切值。这个要从上往下递推。
根节点补集为空：$umin_1=\inf, umax_1=-\inf$。
对于节点 i 的儿子 $v$，v 的补集由三部分组成。
i的补集。i与父节点之间的边切出来的那一大块（权值 $s_1 - s_u, u\ne 1$）。i的其他儿子的子树方向。
\begin{aligned}
umin_v =& \min(umin_u, (s_1 - s_u), \min_{x\in child_u, x\ne v}\min(S_x, dmin_x))\\
umax_v =& \max (umax_u, (s_1 - s_u), \max_{x\in child_u, x\ne v}\max(S_x, dmax_x))
\end{aligned}
线性求“其他儿子”的极值（换根dp）
如果对每个儿子 v 都重新扫一遍所有兄弟，复杂度会退化成 $O(n^2)$。
对每个节点 $u$，预处理它所有儿子分支的候选值：
c_x = \min(s_x, dmin_x), C_x = \max(s_x, dmax_x).
记录这些候选的：
- 最小值
min1与次小值 $min2$，以及最小值来源儿子 $minId$。 - 最大值
max1与次大值 $max2$，以及最大值来源儿子 $maxId$。
计算儿子 v 时：
- 若 $v\ne minId$，兄弟方向最小候选就是 $min1$，否则用 $min2$。
- 若 $v\ne maxId$，兄弟方向最大候选就是 $max1$，否则用 $max2$。
再与 umin_u, umax_u 以及 s_1 - s_u 合并，就得到 $umin_v, umax_v$。
这样每个节点只扫一遍儿子，整体 $O(n)$。
最终求答案
先预处理上述的 $umax, umin, dmax, dmin$。
枚举第一刀的位置 $v$，切成 A, B 两块，分两种情况：第二刀在 A 中或第二刀在 B 中。
第二刀在 A 内部
第二刀切出的 $a \in {dmax_v, dmin_v}$。
三块分别为 $a, A - a, B$，答案为 $median(a, A - a, B)$。
第二刀切在 B 内部。
第二刀切出的 b \in \{umin_v, umax_v\}
三块分别为 $A, b, B - b$，答案为 median(A, b, B - b)
记录最大答案即可。
::::success[code]
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n; // 5e5
vector<int> fri[500005];
int fa[500005];
long long sum[500005];
long long dmin[500005], dmax[500005]; // down max / min
long long umin[500005], umax[500005]; // up 反向的 max和min
int ord[500005];
const long long INF = LLONG_MAX;
const long long _INF = LLONG_MIN;
long long median(long long x, long long y, long long z) {
long long a[3] = {x, y, z};
sort(a, a + 3);
return a[1];
}
int noword;
void dfs(int u) {
ord[++noword] = u;
for (int v : fri[u]) {
if (v == fa[u]) continue;
fa[v] = u;
dfs(v);
}
}
void pre() {
noword = 0;
dfs(1);
int cnt = noword;
for (int i = cnt; i >= 1; --i) {
int now = ord[i];
dmin[now] = INF;
dmax[now] = _INF;
for (int v : fri[now]) {
if (v == fa[now]) continue;
sum[now] += sum[v];
if (sum[v] < dmin[now]) dmin[now] = sum[v];
if (sum[v] > dmax[now]) dmax[now] = sum[v];
if (dmin[v] < dmin[now]) dmin[now] = dmin[v];
if (dmax[v] > dmax[now]) dmax[now] = dmax[v];
}
}
umin[1] = INF;
umax[1] = _INF;
for (int i = 1; i <= cnt; ++i) {
int u = ord[i];
long long min1 = INF, min2 = INF;
long long max1 = _INF, max2 = _INF;
int minid = 0, maxid = 0;
for (int v : fri[u]) {
if (v == fa[u]) continue;
long long mn = sum[v];
if (dmin[v] < mn) mn = dmin[v];
long long mx = sum[v];
if (dmax[v] > mx) mx = dmax[v];
if (mn < min1) {
min2 = min1;
min1 = mn;
minid = v;
} else if (mn < min2) {
min2 = mn;
}
if (mx > max1) {
max2 = max1;
max1 = mx;
maxid = v;
} else if (mx > max2) {
max2 = mx;
}
}
long long pmin = INF, pmax = _INF;
if (u != 1) {
pmin = sum[1] - sum[u];
if (umin[u] < pmin) pmin = umin[u];
pmax = sum[1] - sum[u];
if (umax[u] > pmax) pmax = umax[u];
}
for (int v : fri[u]) {
if (v == fa[u]) continue;
long long amin = (v == minid ? min2 : min1);
long long amax = (v == maxid ? max2 : max1);
umin[v] = pmin < amin ? pmin : amin;
umax[v] = pmax > amax ? pmax : amax;
}
}
}
signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i)
scanf("%lld", &sum[i]);
for (int i = 1, u, v; i < n; ++i)
scanf("%lld%lld", &u, &v), fri[u].push_back(v), fri[v].push_back(u);
pre();
long long ans = _INF;
for (int v = 2; v <= n; ++v) {
long long B = sum[1] - sum[v];
if (dmin[v] != INF)
ans = max(ans, median(dmin[v], sum[v] - dmin[v], B));
if (dmax[v] != _INF)
ans = max(ans, median(dmax[v], sum[v] - dmax[v], B));
if (umin[v] != INF)
ans = max(ans, median(umin[v], B - umin[v], sum[v]));
if (umax[v] != _INF)
ans = max(ans, median(umax[v], B - umax[v], sum[v]));
}
printf("%lld\n", ans);
return 0;
}
::::