题解：CF251E Tree and Table

题解

• 矩形左上（或左下）有一个点，要用这个点的子树铺成一个矩形。
• 矩形左上和左下各有一个点，要用这两个点的子树铺成一个矩形。

• 如果 $x$ 没有儿子，则无解。
• 如果 $sz_x=2$，答案为 $1$。
• 如果 $x$ 有两个儿子，则枚举两个儿子是怎么放置的，设放在下面的为 $u$，右边的为 $v$。
  • 当 $u$ 的儿子个数为 $0$，答案加上 $F(v)$。
  • 否则，$u$ 的儿子个数必为 $1$，答案加上 $G(v,son_u)$。
• 如果 $x$ 有一个儿子：
  • 若子树 $x$ 为一条链，答案为 $\frac{sz_{x}}{2}$。
  • 若 $son_x$ 放在下面，答案加上 $F(son_{son_x})$。
  • 否则找到最浅的有两个儿子的点，设其为 $y$，一直直走直到遇到这个点停止，枚举哪个点向下拐。
    • 如果向下拐的点（设其为 $z=son_{y,0}$）有一个儿子，判断一下它能不能把第二行的前缀填满，如果可以，答案加上 $F(son_{y,1})$。
    • 否则，枚举一下哪个儿子（设其为 $son_{z,0}$）能把第二行的前缀填满，如果可以，答案加上的 $G(son_{y,1},son_{z,1})$。

• 如果 $x,y$ 没有儿子，答案为 $1$。
• 如果 $x,y$ 各有一个儿子，答案为 $G(son_x,son_y)$。
• 否则，设 $x$ 有一个儿子，答案为 $F(son_x)$。