题解：CF2068D Morse Code
george0929
·
·
题解
感觉还是对 DP 过程中算贡献和分布转移的理解不是很深刻。
对二叉树形态 DP，由于节点放置不连续，显然要按深度 DP。
我尝试了在转移时算贡献，但是没有成功，因为最终排名不确定。
事实上，DP 过程中算贡献和分布转移本质上是让每个点实时有贡献，并且固定一些点停止贡献。
对于扩展深度为 $2$ 的点，我们并不用管，因为我们每次只会把点的最浅深度集体下移 $1$，且点只有在作为最浅深度时才会被固定。
**因此这个点的实际深度就是这个点（这个点不存在时我们认为这个点的祖先就是这个点）在状态里的时间 $-1$**。
令 $f_{i,j,k}$ 表示固定了 $i$ 个叶子不再扩展，在未固定的叶子中有 $j$ 个最大深度、$k$ 个次大深度的叶子。
则要么固定一个次大深度的叶子，要么把次大深度的叶子全部扩展。
$$
f_{i,j,k}\to f_{i+1,j,k-1}
\\
f_{i,j,k}+w\to f_{i,k,j+k}
$$
$w$ 表示 $p$ 的第 $i+1\sim n$ 大的和，答案为 $f_{n,0,0}$，构造方案是简单的。
$O(n^3)$。
`double` 要加上 $0.5$ 再转为 `int` 啊啊啊。
[提交记录](https://codeforces.com/problemset/submission/2068/348872685)