成外联测9-A

比赛链接

这道题就随便搞搞 然后显然有一个这样的柿子:i=1nvalj=0mk=0mCmjCmksizeij+k(nsizei)2mjkf(k,j) \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,my)+min(y,mx)f(x,y)=min(x,m-y)+min(y,m-x)valval为这个点到父亲节点的边权。

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

然后就是一个LSJ爷爷在课上讲了的组合恒等式(那天起晚了所以没听到/kk):i=0k(ni)(mki)=(n+mk)\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)

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

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

柿子就变成了:

i=1nvalj=02mC2mjsizeij(nsizei)2mjf(j)\sum_{i=1}^n val\sum_{j=0}^{2m}C_{2m}^{j}size_i^{j}(n-size_i)^{2m-j}f(j)

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