这道题题意很清楚就是求一个稀疏图的独立集数量（稀疏到极点的那种）。

暴力做法也很显然树的情况直接上树形$$DP，有非树边的情况直接枚举非树边两侧端点或特殊點的情况跑树形DP然后加上容斥原理优化就有$$

对于其他题解，我只想说：你们都知道暴力有容斥做法了为什么建完虚树用了个那么诡异的方法

发现转移其实就是一堆乘积，那么就把这些乘积中不变的部分预处理出来

我们处理出每个关键点在虚树上对父亲转移时的系数，鼡矩阵保存

然后直接把暴力的容斥原理优化就可以直接A这道题了啊。

这道题题意很清楚就是求一个稀疏图的独立集数量（稀疏到极点的那种）。

暴力做法也很显然树的情况直接上树形$$DP，有非树边的情况直接枚举非树边两侧端点或特殊點的情况跑树形DP然后加上容斥原理优化就有$$

对于其他题解，我只想说：你们都知道暴力有容斥做法了为什么建完虚树用了个那么诡异的方法

发现转移其实就是一堆乘积，那么就把这些乘积中不变的部分预处理出来

我们处理出每个关键点在虚树上对父亲转移时的系数，鼡矩阵保存

然后直接把暴力的容斥原理优化就可以直接A这道题了啊。