HDU3586 Information Disturbing（Jan. 24th, 2019） 树形DP

动态规划 二分答案 独立解题

$\color{turquoise}{\mathfrak{From\ La\ Pluie\ Froid}}$

题目来源

题意

给定一棵结点数为$n\in[1,10^3]$的树，要求砍掉一些边（带非负权），使所有叶结点与根结点不连通。限制最高花费为$m$，求砍掉的边中最大权值的最小值。

思路

尝试极端方法：严格证明法。

Part 1（整体框架）

$\because$“最大值最小化”，
$\therefore$使用二分答案。
$\because$数据结构为树，
$\therefore$使用图论模板。
$\because$启发式思维[1]，
$\therefore$使用树形DP：设$dp[u][0/1]$表示对于以结点$u$为根的子树，以删除子边$/$删除父边的决策使所有叶结点与根结点不连通的总代价。

Part 2（DP部分）

$\because$删除父边就不用管下面的连接情况，
$\therefore dp[u][1]=\sum min(dp[v][0],dp[v][1]+w[u][v])$。（证伪：“只选择$\color{red}{(u,v)}$”或“继承$\color{red}{dp[v]}$的选择”都可以断绝$\color{red}{v}$的子树中所有叶结点与$\color{red}{u}$的联系）
$\because$不删父边就要删掉所有子边（易证：对于$\forall$有子节点的点$u$，其子节点一定是叶结点或叶结点的祖先），
$\therefore dp[u][0]=\sum (dp[v][1]+w[u][v])$。
最终答案为$dp[1][0]$，因为根结点没有父边。
更正：dp[u]表示对于以结点$\color{red}{u}$为根的子树，使所有叶结点与根结点不连通的总代价。
对于$\color{red}{\forall u}$有$\color{red}{dp[u]=\sum min(dp[v],w[u][v])}$，答案为$\color{red}{dp[1]}$。

Part 3（二分部分）

$\because w_i\in [1,10^3]$，
$\therefore l=1,r=10^3$。
$\because \forall w_i>d$不可删除，
$\therefore$在搜索更新时把$w_i$暂时赋值为$+\infty$。
$\because$叶结点不可删除子边，
$\therefore\ dp[$叶结点$]=+\infty$。

1. $\mathbb{ANS}>m$，说明$mid$小了，以至于无法删去某些效果能够“一条顶多条”的大权边，否则按照$dp$规则，非最优解不可能成为答案，故$l=mid+1$。
2. $\mathbb{ANS}=m$，说明刚好，故$ans=mid$。
3. $\mathbb{ANS}<m$，说明$mid$可能还不够小，以至于删除了一些过大的边取得了更优结果，故$r=mid-1$。

因为$\mathbb{ANS}>m$是非法结果，所以不参与答案统计，所以把$r$和$ans$的更新安排在一起。

反思

1. 理清思路再写题，没有无法战胜的困难，只是没有仔细设计方法。
2. 以最严谨的态度写代码，不允许任何错误。

代码