题解：CF251E Tree and Table

george0929 · 2025-11-16 00:09:35 · 题解

题解

注意到树的度数不超过 4。

当树是一条链时，分类讨论，一定是从某点开始走到头，拐回来走一段之后开始走折线，简单讨论后发现答案是 2(n^2-n+2)，注意链可以翻转，翻转后算不同的方案。

对于一般情况，先放入一个三度点，设其为树根。

当根存在一个儿子是叶子时，两侧被划分为了两个子问题，否则枚举儿子放在哪边，也是两个子问题。

容易发现我们有两种不同的子问题：

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

设第一种为 F(u)，第二种为 G(u,v)。

先讨论 F(x)（假设 x 在左上）。

• 如果 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})。

再讨论 G(x,y)。

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

复杂度看似 O(n^2)，但是提交后直接过了。

因为 G(u,v) 被调用时，两个点的深度差不超过 1，且在 F 中被调用时，两点到 \text{lca}(u,v) 的距离是 O(1) 的，每次 G 往后转移只有一个后继，树的节点度数也是 O(1) 的，因此 G 的总状态是 O(n) 的。

提交记录