用 $n=rc$ 指代地图大小。

首先一个地方到另外一个地方一定是沿着路径最大值最小的那个路径去的，显然是最小生成树，边权设置为两个端点的权值较大值。

考虑 kruskal 重构树，这样从 $x$ 出发不经过路径权值超过 $v$ 能得到的原图的点一定是一个子树的叶子节点。

现在问题就是单点改颜色和子树数颜色，其实有一个非常经典的 trick 叫树链求并。

具体的，当所有叶子颜色都不相同时，让每个叶子 $x$ 都对 $root\to x$ 的路径上权值加 $1$，一个点子树内的颜色数就是这个权值。

注意到，当两个叶子颜色相同时，有一部分点会算重两次，所以需要减去。

推广到一般形式，把颜色相同的所有叶子按照 dfs 序排序，对任意相邻两个节点的 LCA $x$ 执行 $root\to x$ 的路径减 $1$，即可完成去重。

用 set 维护同一种颜色的叶子的 dfs 序，只需要 $O(n)$ 次树状数组修改，复杂度为 $O(n\log n)$。