狼人

在树形dp中处理到结点$x$时，令$dp[i][j]$表示所有以结点$x$为公共祖先的连通分支中，使得$i$种族狼人个数减其他种族总个数为$j$的个数。另外注意到每个$i$是为众数的方案实际上是相互独立的，$dp[i][j]$可仅用于检查$i$为众数的情况，故$j$对$i$的取值范围为$-cnt[i]\sim cnt[i]$，更小$j$的不能构成$i$成为众数的局部方案，更大的则不可能出现。故对所有$i$状态总数实为$O(n^2)$。

考虑递推，更新时初值先考虑子树根$x$必选。对$x$的每个子结点为$y$，有$dp_x[i][j] += dp_x^*[i][j-k]\cdot dp_y[i][k]$，其中$dp_x^*$为考虑该子树前的结果。

考虑复杂度，自下而上归纳证明复杂度为$O(n^2)$。若$n$规模子树的根结点为$x$，不妨认为其$k$个子结点，各自子树的结点数为$S_1,S_2,\cdots,S_k$。则根据归纳假设，子树已经进行的操作消耗不超过$S_1^2,S_2^2,\cdots,S_k^2$，不妨认为$S_1$最大，则可以放缩为$S_1\sum S_i = S_1 n$。然后考虑本轮子树的合并，认为初值为$S_1$对应子树的结果（因为和根结合只相当于其移一位），对$j$按$cnt[i]$放缩，对$k$按$sz[y]$放缩，则求和为$\sum _{子结点y}\sum _{颜色i}(cnt[i]\times sz[y])=(n-S_1)n$，两个求和本都是结点个数，但$S_1$对应子树不用更新。结合子树复杂度，复杂度放缩为$(n-S_1)n+S_1n = n^2$。

考虑答案，注意“连通分支的公共祖先”已经构成所有连通分支的分类，故只需对每一个$x$处的$dp$统计答案，枚举$i$累加$j>0$的$dp[i][j]$即可。时间、空间复杂度$O(n^2)$。