Description

Input

Output

Sample Input

Sample Output

HINT

Source

2013湖北互测week1

orz vfk orz icefox

想做这道题很久了 看网上题解也看了很久了始终明白不了 后来有幸看到icefox巨佬的题解看到了http://vfleaking.blog.163.com/blog/static/17480763420134452440444/

去看一看vfk原来的题解就会豁然开朗

如何hash一棵树 学习了下scarlyw巨佬的blog 就是根据子树大小把子树的hash值都加起来即可 如果专门只求树上独立集计数的话 答案就是设dp[i][0/1]分别表示当前处于i号节点我是否选取当前节点  那么dp[i][1]=显然就是所有子树中不选的乘积

dp[i][0]就是所有子树中选与不选和的乘积

学习了一个组合数学的相关知识 当时bj集训的时候有一道题我看出来是这样做了然而不会算这个的通式 即:有n种物品要求从中选m个求问方案数 那么就是c(n+m-1)(m)

但是这题要求求本质不同的独立集个数 这时候就需要做的时候把所有本质相同的看作一个子树 那么就相当于在这些本质相同中选xx个 利用上面的组合数学相关知识即可解决由于结构不同的子树再怎么弄都不会成为本质 相同的,所以我们将结构相同的子树分成一块

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论