D1T3

考虑转化为求 $\ge i$ 的权值个数 $\ge k$ 的联通块数量。 设 $f(u,i,j)$ 表示 $u$ 子树内含 $u$ 联通块内权值 $\ge i$ 的有 $j$ 个的方案数，$g(u,i,j)$ 维护子树的和，也就是最终答案。发现转移非常简单所以可以写成生成函数： $$ F(u,i) ......

整自闭了，快一个月后才想出来怎么做。 设点 $i$ 是 1 的概率为 $p_i$，定义 $P_i(x)=1-p_i+p_ix$。那么 $p_i$ 是 $i$ 的儿子节点和自己的 $P(x)$ 卷起来后取后一半的系数和。 树上修改很魔怔，考虑 ddp。维护每个点轻儿子和自己的 $\prod P(x)$ ......