[CF1517F] Union

计数好题。关键点在于一步转化，然而我并没有发现。

首先期望转计数，对于这类问题，我们有很经典的处理手法：\(\sum_r\sum_S [f(S)=r]r=\sum_r\sum_S [f(S)\ge r]\)。

但是我并没有发现这一步的意义。事实上，这个条件写到树上就是，存在一个点，使得离它最近的非空闲点距离 \(>r\)。

然后就可以 tree dp 了，设 \(f_{i,j}\) 表示 \(i\) 子树内离 \(i\) 最近的非空闲点距离为 \(j\)，\(g_{i,j}\) 表示 \(i\) 子树内已经满足其子树内部 \(>r\) 限制的点中，离 \(i\) 最远的距离为 \(j\)。初始 \(f_{u,0}=g_{u,0}=1\)。对应空闲/非空闲。

转移：

• \(f_{u,j}\times f_{v,k}\to f_{u,\min(j,k+1)}\)。
• \(f_{u,j}\times g_{v,k}\)，若 \(j+k+1>r\) 则转移到 \(g_{u,k+1}\)，反之转移到 \(f_{u,j}\)。
• \(g_{u,j}\times f_{v,k}\)，类似。
• \(g_{u,j}\times g_{v,k}\to g_{u,\max(j,k+1)}\)。

转移弱于树上背包，单次 \(\mathcal O(n^2)\)，总复杂度 \(\mathcal O(n^3)\)。

总结：计数对象贡献形式的转化可能蕴含着限制条件的转化，时刻关注每一步对问题的影响。