随笔 - 一道树上贪心题

给定一棵 \(n\) 个结点的树，第 \(i\) 个点有点权 \(t_i\), 现在需要断开这 \(n-1\) 条边，定义断开一条边的代价为该边连接的两颗子树中的两个最大点权之和，求最小代价

例如

的最小代价为 \(48\)

解题思路

显然是贪心题

考虑逆向过程，即令初始时这 \(n\) 个点之间没有边，之后逐渐加边构成题面给出的树，定义在点 \(u\) 和点 \(v\) 加边的代价为 \(u\) 和 \(v\) 所在树的最大点权之和，通过调整加边顺序使代价最小

我们首先考虑最优策略

1. 若只有两点 \(a,b\), 显然最小代价为 \(t_a+t_b\)

2. 若只有三点 \(a,b,c\), 且 \(t_a\geqslant t_b\geqslant t_c\), 我们只有两种加边顺序

   1. 若最终的树为 a-b-c 或 a-c-b, 则最小代价为

      \[ \min\{(t_a+t_b)+(t_b+t_c),(t_a+t_b)+(t_a+t_c)\}=t_a+2t_b+t_c \]

      对应的策略为先在 \(b,c\) 间加边，即先在点权较小的点之间加边

   2. 若最终的树为 b-a-c, 则最小代价为 \(2t_a+t_b+t_c\), 与加边顺序无关

3. 若有 \(n\) 个点 \(1,2,...,n\), \(n>3\), 我们发现当加边的代价只与树的最大点权有关，所以在树与树或树与点间加边时，我们可以将树看作点，其点权即为该树中所有点的最大点权，这样便可归为前两种情况讨论

   以在三棵树间加边为例

   

   我们需要在树 \(A,B,C\) 间加边，设树 \(A,B,C\) 之中点权最大的点分别为 \(a,b,c\)

   则我们可以进行缩点，将这三棵树视为三个点 \(A,B,C\), 其点权分别为 \(t_a,t_b,t_c\)

   此时加边代价最小当且仅当如下两条件成立

   • 按最优策略构建树 \(A,B,C\)
   • 按最优策略连接点 \(A,B,C\)

   其中第二条上面已经讨论过，由于树的结点数有限，最终必然会变成要求按最优策略连接两到三个点，这个我们上面也已经讨论过了

由此，我们便得出最优策略：点权大点的后连边

把过程反过来即为：对任意一颗树，优先断开点权最大的点与其余点的连接

接下来考虑如何求最小代价

还是按加边讨论，直接看 \(n\) 个点 \(1,2,...,n,~n>3\) 的情况，显然最小代价必为 \(\sum_{i=1}^nt_i\) 加上某些点权

令构建树 \(M\) 的最小代价为 \(f(m)\), 其中 \(m\) 为其点权最大的点，则对于只有一个结点的树 \(e\), 有 \(f(e)=0\)

下文约定：若点 \(i\) 在树 \(M\) 中，则可记作 \(i\in M\)

先考虑三个点的树和点的连接，以下图为例

设树 \(A\) 中点权最大的点为 \(a\), 则最小代价为 \(f(A)+t_a+t_b\)

我们知道 \(t_b\geqslant t_a\), 且新代价中 \(t_b\) 必然出现，此时的代价多出了 \(t_a\)

继续一个点一个点的加下去，我们不难总结出下式:

构成树 \(M\) 的最小代价为

\[ \sum_{i\in M}t_i+\sum_{x,y\in M;x,y~\text{connected}}\max\{t_x,t_y\}-\max_{i\in M}\{t_i\} \]

而树与树的连接是否也满足该式呢

设树 \(A,B\) 中点权最大的点分别为 \(a,b\), 新边将 \(A\) 中的点 \(x\) 和 \(B\) 中的点 \(y\) 连接起来，最终的树为 \(C\)

则最小代价为 \(f(A)+f(B)+t_a+t_b\)

将 \(f(A)\) 和 \(f(B)\) 代入，又注意到

\[ t_a=\max_{i\in A}\{t_i\} \]

\[ t_b=\max_{i\in B}\{t_i\} \]

故最小代价为

\[ \sum_{i\in C}t_i+\sum_{u,v\in C;u,v~\text{connected}}\max\{t_u,t_v\}-\max\{t_x,t_y\} \]

此时我们回想一下断开边的过程，我们惊奇地发现: \(x\) 就是 \(a\), \(y\) 就是 \(b\)

所以最小代价即为

\[ \sum_{i\in C}t_i+\sum_{u,v\in C;u,v~\text{connected}}\max\{t_u,t_v\}-\max_{i\in C}\{t_i\} \]