首先对于数据范围要有一定敏感度，那么对于 \(k\) 单次求取很可能是 \(O(n)\) 复杂度，或者对于所有 \(k\) 做一个 \(O(n^2)\) 的 DP 之类的做法。
观察到，不确定根的情况是非常难搞的，整个路径信息都会遍历，所以我们其实不太好根据这个东西做换根，但是此时对于每个根显然是无法 \(O(n)\) 求出答案的（这是东西用 DP 至少记录两维，而且没有什么凹凸性质之类的），所以我们不能朝着换根的角度去想。
换一个思考点，根并不重要，只需要对于当前你设置的次要位置求出能作为根的位置有多少个就可以了，明眼人都看得出来这个东西应该比上面那个东西好求。
那么我们简化一下这个问题，什么时候有能作为根的位置，我们声明当且仅当不存在两个次要位置相邻且不存在三个点在一条链上。第一点比较好理解，第二点是无论你从哪个点为根，都会有 LCA 将其中的两个点分到一条链上，于是不行，这说明了这个条件的必要性，这个性质已经可以强到说明充分性了（可以构造证明）。
考虑对于每种情况，方案数相当于 \(n - \sum siz_i\)（以某个点作为首都的情况），使用 \(f, g\) 进行树形背包即可。
关键是想到对根计数。