ABC235H

ABC235H Painting Weighted Graph

Description

给定一个 个点 条边的无向带权图，初始时点全为黑色。

你可以在这张图上进行不超过 次操作，每次操作可被描述为如下形式：

1. 选择一个点 和一个整数 。
2. 将所有从点 出发，只经过边权不大于 的边 能到达的所有点 染红。

设所有被染红的点构成的点集为 ，求不超过 次操作后能构成多少个不同的 。

答案对 取模。

Sol

看到“边权不大于”想到Kruskal重构树。建出重构树后，问题转化为：

在树上选取 个关键点并将子树中的所有叶结点染色，求能得到多少种不同的树。

考虑经典树上背包。

在 子树内选取 个关键点，叶节点的染色方案数。

转移：

但是这个 DP 有一些小问题：

• 如果两个树上的非叶节点边权相同，那么就会算重。
  • 解决方案：建树时合并边权相同的结点。
• 子树全选的方案和只选子树根的方案重复，且没有只选子树根的方案。
  • 解决方案：计算完毕后 。

时间复杂度 。

Code

我太菜了，咕咕咕。