【CERC2017】Embedding Enumeration

Description:


给你一棵\(n\)个节点的树,要求你将结点填入一个两行无穷列的网格中,要求点1 在左上角,有边相连的结点在相邻的格子中,求方案数模\(10^9+7\)。

\(1\leq n\leq 300000\)

Example:


input output
5
1 2
2 3
2 4
4 5
4

Solution:


太神了!

\(dp[i]\)表示只剩\(i\)的子树没有填,\(i\)放在左上角,且\(i\)左侧的格子不能再填入,的方案数。

然后我是看这篇博客才看懂的 Orz

然而我最后还是只写了个\(n log(n)\)的,不知道 jump(x, y)怎么优化了。

然后写完还调了好久,都是一些傻逼错误,什么if里&&写成==啊,倍增数组忘记初始化啊,边界情况没判啊。。。

具体细节看代码。

Code:


 



1 评论

发表评论

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