[CF 251E]Tree and Table题解翻译

题解翻译


如果N=1,则答案为2.

如果树中存在一个度数大于3的节点在,则答案为0.原因是网格中的每个格子的邻居数不超过3.

如果树中没有度数为3的节点,则答案为2N^2-2N+4.这一公式可以在题目其他部分的解答中自然地推导出。同时,我们也可以写一个简单的DP来计算这种情况下的答案。无论如何,我们现在证明这一公式。

首先,我们解决一个略有不同的问题,它在原问题的一个主要情况中也能用到。我们希望找出将一棵所有节点度数小于3的树放在网格中的方案数量,使得一个度数为1的点被放在左上角的格子中(令它为1号节点)。我们发现,如果网格的大小是2*K,则放置方案数等于K。这一公式可以用数学归纳法证明。如果K=1则结论显然成立。假设K>1,并且网格被横向放置,使得它有2行K列。如果我们把和1号节点相邻的节点放在左上角格子的右边(译者注:即(1,2)),则只有一种放置方案。而如果我们将这个节点放在左下角,则下一个顶点应当放在(2,2),问题化归为K减小1的情况。因此我们有递推关系f(K)=f(K-1)+1而且已知f(1)=1.这意味着f(K)=K。

让我们回到计算将节点度数小于3的树放在2*N网格上的方案数的原问题。不失一般性地,不妨设1号节点的度数为1.我们将只考虑1号节点在第一行中的放置方案,并在最后将答案乘以2.如果1号节点在第一列或最后一列,则有N种放置树的方法(见上一段)。如果1号节点在第i列,那么有i-1种将1号节点的相邻节点(不妨设为2号节点)放在1号节点右边的方案,类似地,有N-i种将2号节点放在1号节点左边的方案。对每一行将这些答案加起来并乘以2我们便得到了最终答案:2N^2-2N+4.

现在我们只需要解决树中存在度数为3的节点的问题了。我们不妨令这一点为根。如果有多个度数为3的节点,选择其中任意一个作为根。我们假设根放在第一行,而最终将答案乘以2.显然,根应当放在一个有3个邻居的格子中。根的三个儿子应该被分别放在根所在格的左边,右边和下边。让我们明确这一顺序(为此需要遍历6种排列)。并且,如果“下边的”儿子的度数大于1,我们还需要明确其相邻格节点的顺序(有2种情况)。现在,根所在的一列已经被填满。这一结论意味着无论我们如何放置余下的节点,位于根右侧的节点将始终位于根右侧。对根左侧的节点也一样。此外,我们已经确定了根左侧的节点数,这意味着根在网格中的位置是确定的。注意到如果根左侧的节点数是奇数,将没有合法的放置方案。为了找出根左侧的顶点数,我们需要将根左边儿子的子树大小相加,再加上根下边儿子左边的后代。

因此,我们现在有了两个单独的子问题(分别对于根左侧和右侧的节点),对于其中的每一个,我们都需要计算将余下的树放在网格中的方案数。有两种可能的情况:

1)我们需要将一棵以节点v为根的子树放在一个矩形子网格上,使得v位于角落(假设它是左上角)。

2)我们需要将以为v1和v2为根的两棵子树放在矩形子网格上,使得v1在左上角而v2在左下角。

显然,若子树大小之和为奇数,则以上两个问题都无解。

下面我们将第二类问题简化成第一类问题。如果v1或v2有两个儿子,则答案为0.如果它们都有一个儿子,那么我们需要对它们的儿子解决同样的问题,显然答案也相同。如果v1和v2都没有儿子,那么答案为1.最终,如果两个节点这一有1个儿子而另外一个儿子,那么我们就对于v1和v2的唯一一个儿子得到了一个第一类问题。

下面只需要解决第一类问题。令f(v)为将以v为根的子树放在矩形网格上的方案数。网格的大小由子树大小唯一确定。让我们考虑两种情况:

a)节点v的度数为2.

b)节点v的度数为3.

若v的度数为2而且子树中没有度数为3的节点,则f(v)=s(x)/2,其中s(v)是以v为根的子树的大小。我们已经在上面证明了这一公式。现在我们假设在以v为根的子树中有至少一个度数为3的节点。如果有若干个度数为3的,我们选取离v最近的那个。设其为节点w.对此有两种可能的情况:

a.1)v到w的路径中,w的上一个节点在网格中w的左边。

a.2)v到w的路径中,w的上一个节点在网格中w的上边。

易证没有第三种可能性。

在两种情况a.1)和a.2)中,我们确定w的儿子的方向(一个方向已经被w的父亲占据,因此实际上只有2种可能的方向)。若度数大于1的儿子和w在同一列,我们还需要再确定其儿子的方向。在这之后我们就对节点w的右侧得到了类型1)或2)的问题。对于w的左侧我们有一棵树,它要么无法放在网格中,要么恰好有1种放法。为了判断这一点,我们需要检查从v到w的路径长度以及w的孙子的子树大小,它位于w的右侧(显然它存在)。现在我们需要将所有可能的答案加起来。

因此我们得到了a)类问题的答案。还余下b)类问题,即v的度数为3的情况。为了解决这个问题我们需要确定其儿子的方向,在此之后我们将得到一个类型1)或类型2)的问题,如前所述。

答案复杂度为O(N)。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注