【ZJOI2016】小星星


我们对于这一类计数问题,考虑容斥来做

这道题目其实就是对树上的结点进行重新标号,使得树上存在边的在图中也存在

那么,我们用\(f[i][j]\)表示树上结点\(i\),对于图中标号\(j\)的方案数

显然\(f[i][j]=\prod_{}^{} (\sum f[x][k])(x\in C(i),(j,k)存在)\),树形dp,时间复杂度\(O(n^3)\)

暴力枚举容斥的状态\(O(2^n)\),总的时间复杂度是\(O(2^n*n^3)\),再卡卡常数就过了

 

You may also like

LEAVE A COMMENT

Statistics

  • 0
  • 8,107

Categories

Archive

Comments