某岛

… : "…アッカリ~ン . .. . " .. .
September 22, 2011

.. . A unknown sequence ….

副标题叫做:关于轻重边树链剖分的一个组合问题。。。

.. .
回顾一下那 4 关于树的计数问题 .. ,

下面有一个新的问题:
给定所有形态的无根树,问对她们进行轻重边树链剖分后产生的不同的树的总数。。。

显然这个问题也可以根据有无标号、有无根分成 4 种,但是其实只有无标号 + 无根最有意义(似乎也不是)。
。。对于任何形态的树,其轻重边树链剖分的结果不一定是唯一的,(但是不同形态树一定不会剖分成一颗相同形态的。。。吧。。)
。。。然后发现这个问题还不够明确。。因为关于树链剖分本身就有一些不同的定义,我目前知道的就有。三种。。(。那么现在就已经有 12 个有待解决的问题。。。)

。。。那么暂时只考虑对边进行二染色.. . 要求黑色的边只形成一些路径。。。
。。。。。。(现在这个问题定义的良好多了。。。。谁能教教我呢。。)。。。


这里画出 n = 5 的情况,注意到 n = 5 只有 3 种形态不同的树,其中星形的是最容易进行计数的,(只需要考虑 0,1,2 染色三种情况各一次。)。。
其次是线形的。(。因为总不会产生重路径被破坏的情况,只有一个含有翻转的置换群,可以用 Polay 解决。。)
。。注意第三种形态有一种三染色的方案产生了一个度数为 3 的结点被删去了。。(这也是这个问题的难点所在。。)
)

(图搞错了。。)

.. 1, 1, 2, 3, 8, 23 ..

… .