树上背包的复杂度问题

考虑这样的一个情景,需要进行的操作是对每一个节点求\(f_{v,i}\times f_{u,j}\)其中\(u=fa(v)\)，\(i\in[1,siz_v],j\in[1,siz_u-siz_v]\)。那么对每一个进行操作就是\(\sum_{siz_v\times (siz_u-siz_v)}=\sum_{u,v}{siz_v\times siz_u-siz_v\times siz_v}\)。又因为\(siz_u=1+\sum_{siz_v}\)，所以就变成了\(\sum_{u,v}{siz_u\times (siz_u-1)-siz_v\times siz_v}\)所以就是\(n^2\)的。