Luogu7422 「PMOI-2」城市

题意：给出一张 个点 条边的无向图。每个点有自己的颜色。

• 若点 到 的任意两条简单路径边不相交，则称 关于 互不影响。

• 若点 到节点 的任意简单路径边经过点 ，则称 必经 。

设 为满足下列条件的 元集合 的个数。

• 中所有点颜色相同，且与 的颜色不同。

• 对于任意 ， 必经 。

• 对于任意 ， 关于 互不影响。

给出参数 ，求下列式子的值：

答案对 取模，，，，时限 。

---

建立广义圆方树，以 为根。

若 必经 ，则在圆方树中 是 的祖先。

故在 中，集合 必定在 的子树内。

此时， 互不影响当且仅当他们在 的不同子树内。

分别计算 与 。

• 即统计树上异色祖孙点对数，一次 dfs 并记录栈中颜色即可完成。

• 枚举 中的颜色，对每种颜色分别计算。

  由于集合大小至少为 ，若对该颜色的点建立虚树，则只有虚树中的点可能有贡献。

  现在问题转化成：点有黑白两色，要求 中的点必为黑色，其余规则与 相同，设方案数为 。

  考虑如何对单个点 求出 。

  若该点有 个子树，设第 个子树中的黑点个数为 。

  考虑 ，设 为考虑了前 个子树，选取了 个点放入 的方案数，显然有转移：

复杂度为 。

虚树中的点的子树个数和是 的，不难证明最大复杂度是 。

总复杂度为 。