考场上最后1h才会，成功没写完。
先考虑个暴力，\(f_{i,j}\) 表示 \(i\) 次操作后 \(tag_j=1\) 的方案数，\(g_{i,j}\) 表示 \(i\) 次操作后 \(j\) 号点到根的路径上的点 tag都是0 的方案数。
定义终点，途径点，终点子树（不含终点），途径点儿子（不含途径点），途径点儿子子树（不含途径点，途径点儿子）为字面意思。
设 \(G=g_{i-1,j},F=f_{i-1,j},g=g_{i-1,j},f=f_{i-1,j},mul=(\frac{(n+1)*n}{2})^{i-1}\)
对于每种可能的操作，有如下转移：
对于终点，\(f+=mul\)
对于途径点，\(g+=mul\)
对于终点子树，\(f+=F\)
对于途径点儿子，\(f+=mul-G,g+=G\)
对于途径点儿子子树，\(f+=F,g+=G\)
发现每个点独立，k很大，考虑对每个点做矩阵快速幂。
设终点，途径点，终点子树，途径点儿子，途径点儿子子树数量分别为\(c1,c2,c3,c4,c5\)。
\[\begin{bmatrix} f & g & mul \end{bmatrix} = \begin{bmatrix} F & G & mul' \end{bmatrix} \times \begin{bmatrix} (c3+c5) & 0 & 0 \\ -c4 & c4+c5 & 0 \\ c1+c4 & c2 & \frac{(n+1)*n}{2} \end{bmatrix} \]
如果求出了c*，答案可在 \(O(3^3nlogk)\) 内求出。
求c*实际上只需求出c1,c2。
可以通过某个线段树上经典结论在 \(O(n)\) 内求出（这过几天再补做法）