题意理解

我们有一棵 $n$ 个节点的树，要给每条边染上 $k$ 种颜色之一。给定 $m$ 条路径（由节点对确定），要求每条路径都是“多彩的”，即路径上的边至少包含两种不同的颜色。求满足条件的染色方案数，对 $10^9+7$ 取模。

数据范围：$n \leq 60$，$m \leq 15$，$k$ 可以很大（最多 $10^9$）。

核心思路：容斥原理

问题转化 直接计算所有路径都多彩的方案比较困难，我们考虑用容斥原理。

设第i条路径是单色为一个坏事件。我们要求的是：

ans = 总方案数 - 至少一条路径单色的方案数 + 至少两条路径单色的方案数 - 至少三条路径单色的方案数 + ...

用容斥原理表达：

ans = 对所有路径子集S求和：(-1)的S大小次方 × F(S)

其中F(S)表示让集合S中所有路径都是单色的染色方案数。

计算 $F(S)$

关键观察：如果 $S$ 中所有路径都是单色的，那么这些路径覆盖的边集 $E_S$ 中，每个连通分支必须染同一种颜色。

证明：

• 如果两条边在 $E_S$ 中连通，那么它们必须同色（因为存在路径同时包含它们，且该路径是单色的）
• 因此 $E_S$ 的每个连通分支内部颜色相同
• 不同连通分支之间颜色选择独立

设 $E_S$ 形成 $c(S)$ 个连通分支，则： [ F(S) = k^{,c(S)} ] 因为每个连通分支可以独立选择 $k$ 种颜色之一。

算法步骤

1. 预处理路径边集

对于每条路径 $i$（端点 $c_i, d_i$）：

• 找到路径上的所有边
• 可以用 DFS 或 LCA 实现
• 存储为位掩码或布尔数组

2. 枚举子集 $S$

由于 $m \leq 15$，可以枚举所有 $2^m$ 个子集：

• 用二进制位表示每条路径是否在 $S$ 中
• 对每个 $S$，计算边集并集 $E_S$

3. 计算连通分支数 $c(S)$

对每个 $S$：

• 取 $S$ 中所有路径的边集并集
• 用并查集或 DFS 计算 $E_S$ 的连通分支数 $c(S)$

4. 容斥计数

对每个子集 $S$：

• 计算贡献 $(-1)^{|S|} \cdot k^{\,c(S)}$
• 累加到答案中
• 所有运算对 $10^9+7$ 取模

5. 快速幂

由于 $k$ 可能很大（$10^9$），计算 $k^{\,c(S)}$ 需要用快速幂。

复杂度分析

• 预处理：$O(nm)$ 或 $O(n^2m)$，用于找出所有路径的边集
• 主算法：$O(2^m \cdot n)$
  • 枚举 $2^m$ 个子集
  • 对每个子集，用并查集计算连通分支数（$O(n)$）
• 总体：$O(2^m \cdot n)$，在 $m \leq 15$，$n \leq 60$ 时可行

总结

本题是容斥原理的经典应用：

1. 将"所有路径都多彩"转化为"至少一条路径单色"的补集
2. 利用路径单色意味着边集连通分支同色的性质
3. 通过枚举子集和计算连通分支数实现容斥

这种方法在 $m$ 较小时非常有效，是处理"多个条件同时满足"计数问题的通用技巧。