HDU 5121 Just A Mistake (树形dp,组合数)

给出一颗树,按照某个顶点序号的排列,按照顺序将点加入集合(于集合内点没有变),这样每种排列会构造出一种独立集,求独立集size的期望 * N!

考虑计算每个点一定选的时候贡献的方案数,那么每个点总和的方案数就是答案。
dp[i][j]表示i子树在子树编号中是第j个时的方案数,接着用组合数学转移一下,考虑将当孩子v节点分成两半放到u的前面和后面 。

 

LEAVE A COMMENT