HDU 5977 Garden of Eden

时间:2024-09-05 12:07:14

题解:

路径统计比较容易想到点分治和dp

dp的话是f[i][j]表示以i为根,取了i,颜色数状态为j的方案数

但是转移这里如果暴力转移就是$(2^k)^2$了

于是用FWT优化集合或

另外http://www.cnblogs.com/sclbgw7/p/9508235.html给出了一种技巧优化空间

就是我们优先处理重儿子,这样子我们上面记录的状态一定都是连着轻边的

而由树链剖分的复杂度证明我们可以知道一条路径上轻边最多只有log条

为什么呢,因为重儿子肯定比轻儿子大,所以至少翻倍