查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转长链剖分模板长链剖分优化 dp 设$f_{x,i}$表示$x$子树内与$x$距离为$i$的点的个数$$f{x,i}= \sum f{to,i-1}\\(f_{x,0}=1)$$可以发现$x$从它的儿子继承答案这时就可以用长链剖分优化 dp 了(一种类似$\text{dsu on tree}$的方法)设$len_x$为$x$到叶节点的最长距离我们将$\max len_{to}$设为$x$的重儿子$x$直接继承重儿子的答案,而不用重新再算一次其他的儿子再按普通方式计算因为每条链只会被合并一次,因此总复杂……