题解 P6748 【『MdOI R3』Fallen Lord】

a___ · 2020-08-10 17:08:55 · 题解

update(20/8/18):感谢@loveJYdalao指出错误。

算法标签：\color{#FFFFFF}\colorbox{#E74C3C}{\small\texttt{树上dp}}\ \color{#FFFFFF}\colorbox{#E74C3C}{\small\texttt{贪心}}

这题其实很好写，就是dp状态不太好想。

前置芝士：一个数列的中位数小于等于 x \Leftrightarrow 一个数列有至少 \left\lfloor\dfrac{len}{2}\right\rfloor+1 个数小于等于 x。

记 \operatorname{val}(u,v) 表示边 (u,v) 上的边权（或者叫做军队战斗力）。

首先，显然没有无解的情况，因为如果每条边权都置为 1，无论如何都不会有人造反。

然后，由于以上性质我们发现对于一条边的边权 我们只关心其是否大于两端点点权，于是
设 f_{u,0/1} 表示
当 \operatorname{val}(\operatorname{fa}(u),u)\leq a_u\ \ /\ \ \operatorname{val}(\operatorname{fa}(u),u)> a_u 时 以点 u 为根的 子树内 满足条件的 边权和的 最大值。
设 g_{u,0/1} 表示
当 \operatorname{val}(\operatorname{fa}(u),u)\leq a_{\operatorname{fa}(u)}\ \ /\ \ \operatorname{val}(\operatorname{fa}(u),u)> a_{\operatorname{fa}(u)} 时 \operatorname{fa}(u) 的子树 u，包括边 (\operatorname{fa}(u),u)， 边权和的最大值。

举个例子：

以点 5 为例，其周围有 3 条边，则应存在 2 条边边权小于等于 40。当边 (2,5) 边权小于等于 40 时，向下可以有一条边权大于 40，所以 f_{5,0}=30+50。

显然，如果我们以点 1 为根dfs，最后答案为 f_{1,0}。

接下来是状态转移。

1. 已经算出 \forall v\in \operatorname{son}(u)\ \ \ \ g_{v,0/1}，求 f_{u,0/1}：
   考虑贪心。我们先选所有 g_{v,0}，即使所有到儿子的边的边权都小于点 u 点权。对于 f_{u,0} ，此时可以有 \operatorname{du}(u)-\left(\left\lfloor\dfrac{\operatorname{du}(u)}{2}\right\rfloor+1\right) 条边的边权大于点 u 点权；对于 f_{u,1} ，此时可以有 \operatorname{du}(u)-\left(\left\lfloor\dfrac{\operatorname{du}(u)}{2}\right\rfloor+1\right)-1 条边的边权大于点 u 点权。设允许的边权大于 a_u 的边数为 k，我们从大到小枚举 k 个 g_{v,1}-g_{v,0}，即贪心地考虑将小于 a_u 的边换成大于 a_u 的边即可。
2. 已经算出 f_{u,0/1}，求 g_{u,0/1}：
   分类讨论：
   1. a_u<a_{\operatorname{fa}(u)}
      1. g_{u,0}
         1. a_u<\operatorname{val}(\operatorname{fa}(u),u)\leq a_{\operatorname{fa}(u)}
         2. \operatorname{val}(\operatorname{fa}(u),u)\leq a_u<a_{\operatorname{fa}(u)}
      2. g_{u,1}
         1. a_u<a_{\operatorname{fa}(u)}<\operatorname{val}(\operatorname{fa}(u),u)\leq m
   2. a_u=a_{\operatorname{fa}(u)}

      直接并入1或3

   3. a_u>a_{\operatorname{fa}(u)}
      1. g_{u,0}
         1. \operatorname{val}(\operatorname{fa}(u),u)\leq a_{\operatorname{fa}(u)} <a_u
      2. g_{u,1}
         1. a_{\operatorname{fa}(u)}<\operatorname{val}(\operatorname{fa}(u),u)\leq a_u
         2. a_{\operatorname{fa}(u)}<a_u<\operatorname{val}(\operatorname{fa}(u),u)\leq m

综上：

然后从下向上dp即可。

注意到当 \operatorname{du}(u)\leq 2 时，无论如何不可能出现 \operatorname{val}(\operatorname{fa}(u),u)>a_u。此时，需特判将 f_{u,1} 置为 -\inf。

AC代码