看到这个题面只想起了 [WC2019] 数树 。
于是按照那题的方法推,推出来答案是下面这个式子(写了暴力验证是对的):
\[\sum_{S\subseteq T} (x-1)^kn^{k-2}\prod_{i=1}^{k}a_i
\]
发现如果 \(x\) 是确定的数就可以套数树 sub2 的 dp 做法做到 \(O(n)\) 。于是代 \(n\) 个值进去求是 \(O(n^2)\),再插值出多项式就是 \(O(n^2)\)。
上面都是自己瞎想的,不一定对。
刚想写这个做法然后 zaky 就说是原题,还是我做过的,我真就毫无记忆力。。。