【CERC2017】Embedding Enumeration

Description:


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

\(1\leq n\leq 300000\)

Example:


inputoutput
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:


 

3 评论

  1. Wernicke Wernicke’s and korsakoff’s syndromes These syndromes are disorders in the human central nervous system (CNS), which result from the Combination…
    anxiety disorder meaning in hindi
    Comparasion of regional cerebral oxygenation between inhalation and intravenous anaesthesia in patients undergoing laparoscopic surgery ruЕѕman, tomislav – europeana collections anoxemia

发表评论

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