一份题解_DL24袁小迪

作业

T1 Drop

首先，如何用一个二进制数表示一条路径？

可以设计这样一种方案：

从深度为i（根节点深度为0）的点往左走，则二进制数的第i位是0；向右走，则第i位是1。（第0位是最低位）

我们发现，每有一个小球落下，它的路径二进制数就是上一个小球的路径二进制数 + 1。

那么我们只要把路径二进制数转化为点的编号即可。只需把这个二进制数左右颠倒过来（例如 10010 变成 01001）然后在最左边加一个1即可。

T2 Cut

DFS（树形DP？）

把子树中所有正的DP加起来即可。

T3 TSGL

用左二子右兄弟版（链前版）的Trie树即可。