首先思考 (D=1) 怎么做.
不难发现,如果一个时空隧道指向了一个必胜点,那么这个时空隧道相当于不存在;否则相当于强制把这一层的某个点 (x) 变为了必胜点.
换根 DP 求出 (cnt_x) 表示能使 (x) 胜负状态改变的强制把这一层的某个点 (y) 变为了必胜点的操作种数.
记原树上的必胜点数目为 (cntw) ,必败点数目为 (cntl) ,记 (win_x) 表示原树上 (x) 是否必胜,是则为 (1) ,否则为 (0) .
那么对于 (D=1) ,答案就是 (cnt_1 imes cntl + win_1 imes n imes cntw) .
记 (fw_i) 为 把 (i) 强制变为必胜点之后的必胜点数目,特别的,令 (fw_0=cntw) . 记 (sumcntw) 为 (sumlimits_{i=1}^n fw_i)
记 (fl_i) 为 把(i)强制变为必胜点之后的必败点数目(,)特别的(,)令 (fl_0=cntl) . 记 (sumcntl) 为 (sumlimits_{i=1}^n fl_i)
对于 (D>1) 的情况(,)首先我们考虑 (dp_{i,x(1leq xleq n)}) 表示第(i)层的时空隧道连接了下一层的必败点(,)并使得(x)强制变为必胜点的方案数.
再记一个 (dp_{i,0}) 表示示第 (i) 层的时空隧道连接了下一层的必胜点的方案数.
如果我们能计算出这些东西(,)那么答案就是 (sumlimits_{i=0}^n dp_{1,i} imes (cnt_1 imes fl_i+win_1 imes n imes fw_i))
那么怎么 DP 呢?
(dp_{i,x(x>0)} = sumlimits_{y=0}^n dp_{i+1,y} imes fl_y)
(dp_{i,0}=sumlimits_{y=0}^n dp_{i+1,y} imes fw_y)
不难发现所有的 (dp_{i,1},dp_{i,2},...,dp_{i,n}) 都相等,所以对于每个 (i) 我们只需要记两个 DP 值.
并且转移可以写成矩阵形式,而且无论是转移还是计算答案我们都不需要求出 (fl_i) 和 (fw_i) ,只需要求出它们的和 (sumcntw) , (sumcntl) . 这两个数可以通过上述的换根 DP 结果求出.
复杂度 (O(n+log D)) 或 (O(nlog n+log D)) 细节非常多.
(O(n + log D)) 代码 ：见云剪贴板
注意实现时的空间！！！注意实现时的空间！！！注意实现时的空间！！！
不建议使用vector存图/map存DP结果.