成外联测9-A

比赛链接

这道题就随便搞搞 然后显然有一个这样的柿子：$\sum_{i=1}^n val\sum_{j=0}^{m}\sum _{k=0}^{m}C_m^jC_m^{k}size_i^{j+k}(n-size_i)^{2m-j-k}f(k,j)$

其中$f(x,y)=min(x,m-y)+min(y,m-x)$，$val$为这个点到父亲节点的边权。

然后我们又发现，当$x+y\leq m$，$f(x)=x+y$。当$x+y>m$，$f(x)=2m-x-y$。只有这两种情况。所以$f(x+y)=min(x+y,2m-x-y)$。

然后就是一个LSJ爷爷在课上讲了的组合恒等式（那天起晚了所以没听到/kk）：$\sum_{i=0}^{k}\left(\begin{array}{l}n \\ i\end{array}\right)\left(\begin{array}{c}m \\ k-i\end{array}\right)=\left(\begin{array}{c}n+m \\ k\end{array}\right)$

其实就是合并组合数 ：$\sum_{x=0}^n \sum_{y=0}^m C_n^x C_m^y = \sum_{p=0}^{n+m} C_{n+m}^p$。前面的这玩意就相当于前一半选多少个方案数乘上后一半选多少个的方案数，显然就等于把前后两半合在一起选的方案数。

然后你会发现，在用了这两个操作之后 就不需要分别枚举$x$和$y$了，枚举个$x+y$就好了。

柿子就变成了：

$\sum_{i=1}^n val\sum_{j=0}^{2m}C_{2m}^{j}size_i^{j}(n-size_i)^{2m-j}f(j)$

然后这玩意复杂度就是$O(nm)$的啦～