9.18 比赛总结

题目。

A,B 水，D 随便一种算法找环，然后随便一种数据结构维护。

C：两个点等价，当且仅当以两个点为根的树同构。

如果存在一个点不与其它点等价，则以这个点作为根，否则一定有两个连有边的点等价，断开这条边形成两棵同构的子树。经过这步处理之后，等价的点一定在相同深度。

状态采用一般的树上最大独立集思路，\(f_{u,0/1}\) 表示以 \(u\) 为根的子树中，不同的情况。不等价的儿子直接乘，如果有 \(k\) 个儿子等价，设每个有 \(n\) 中情况，是个可重集组合，答案是 \(C_{n+k-1}^{k}\)。

计算这个组合数，展开得 \(\dfrac{n(n-1)(n-2)\dots(n-k+1)}{k!}\)，上下分别计算（可以取模），时间复杂度 \(O(k)\)，总时间复杂度 \(O(n)\)。

对于上述的第二种情况，分根是否有 \(1\)，有则确定为第一个，没有则总方案加上两边一样的方案，再除以 \(2\)。

有的时候，DP 需要和一些组合计数结合。多找一些深入的性质。