MOCK CSP-S 20220302 D – Trees 题解转录

考虑一棵无根树的生成方式:需要决定一个好的顺序从而达到不重不漏地生成所有 nn 个点的无根树。

类似有向无环图的拓扑排序,可以定义一种无根树的“拓扑排序”:每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 rr,则当最终剩余一个孤点时,直径 d=2rd=2r,否则直径 d=2r1d=2r-1。为了生成无根树,我们考虑进行逆操作,在当前的树上加叶子。在此之前,为了不重不漏地对无根树进行表示,我们考虑如下的唯一表示方法:设 dis(x)\text{dis}(x) 为节点 xx 在添加叶子过程中第几轮被添加上树的。对于S={xdis(x)=const}S=\{x\mid \text{dis}(x)=\text{const}\}(也即同一层的节点),显然两棵有标号无根树同构但标号不同,当且仅当每个上述节点xx的叶子节点的标号集合不同。我们总是将 xx 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构,子节点编号集合相同导致重复计数的问题”。同时,为了方便、准确地计算,我们严格规定,新加入的 kk 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。

f(i,j)f(i,j) 为当前这棵树是具有 ii 个节点,且有 jj 个叶子节点的带标号无根树个数。怎么转移呢?设新添加了 kk 个叶子。设长度为 kk 的序列 pp ,其中 pqp_q 表示第 qq 个叶子添加到的树上的标号,每个位置有 ii 种取值,并且这个序列必须出现给定的 jj 种取值,设这种序列的个数为 g(i,j,k)g(i, j, k), 那么转移就是f(i+k,k)=kjf(i,j)g(i,j,k)(i+kk)f(i+k,k)=\sum\limits_{k\geq j}f(i,j)g(i,j,k)\dbinom{i+k}{k}。最后的二项式是指从现在的 ii 个点中选出 kk 个作为这一轮的叶子的编号。不存在排列数,因为我们总是按照编号大小依次添加到每个当前的叶子节点上。

接下来考虑 gg 的求解。对于单个 g(i,j,k)g(i,j,k),可以在预处理组合数后 O(j)\mathrm{O}(j) 的时间内采用容斥原理计算。但我们需要高效地转移相关联项。考虑往长度为 kk 的序列中新加一个元素,有两种情况:要么这是一个之前没有出现过的,并且是特殊值(即必须至少出现一次的值),要么是之前出现过的特殊值或者其不是特殊值。第一种情况,为了产生新的序列,应该将最后的元素与前面的互换位置,那么就有g(i+1,j+1,k+1)(j+1)×g(i,j,k)g(i+1,j+1,k+1)\leftarrow(j+1)\times g(i,j,k)。可以发现,对于任意一个不重复的具有如上参数的序列,在任意位置新插入一个从未出现的特殊元素生成的新序列都是唯一的。第二种情况,这个元素必然是原来 ii 种取值之中的其中一种,去掉之后仍然是一种子问题,那么就有g(i,j,k+1)i×g(i,j,k)g(i,j,k+1)\leftarrow i\times g(i,j,k)

有了 f,gf,g,原问题也就不难求解了。设 h(i,j)h(i,j) 表示当前是 ii 标号的有 jj 个叶子的无根树的直径和。其转移与 ff 类似,考虑 h(i,j)h(i,j)h(i+k,k)h(i+k,k) 的转移。此时的直径分为两部分:旧树直径与新叶子。对于新叶子而言比较容易,根据之前的分析,加一轮叶子的贡献固定为 22,同时采用与ff相仿的转移,那么就有 h(i+k,k)2f(i,j)g(i,j,k)(i+kk)h(i+k,k)\leftarrow 2f(i,j)g(i,j,k)\binom{i+k}{k};对于旧树直径,就只需要考虑新树对于旧树而言会有多少种新树,采用新增序列 g(i,j,k)g(i,j,k) 和组合数进行转移。于是就有h(i+k,k)=kj(2f(i,j)+h(i,j))g(i,j,k)(i+kk)h(i+k,k)=\sum\limits_{k\geq j}\left(2f(i,j)+h(i,j)\right)g(i,j,k)\dbinom{i+k}{k}

初值有 f(1,1)=f(2,2)=1f(1,1)=f(2,2)=1i[0,n],g(i,0,0)=1\forall i\in[0,n], g(i,0,0)=1h(2,2)=1h(2,2)=1。最终答案为ans=i=1nh(n,i)\text{ans}=\sum_{i=1}^{n}h(n,i)。时间复杂度O(n3)\mathrm{O}(n^3)

  • 2022年3月4日