問題
$N$ 頂点の木 $T$ が与えられる。$K$ 色を使って、隣接する頂点が異なる色になるように彩色する方法の数を $10^9 + 7$ で割った余りを求めよ。$Q$ 個のクエリが与えられ、各クエリで $K_i$ の値が変わる。すべてのクエリに答えよ。
制約
| パラメータ | 範囲 |
|---|---|
| $N$ | $2 \le N \le 2 \times 10^5$ |
| $Q$ | $1 \le Q \le 2 \times 10^5$ |
| $K_i$ | $1 \le K_i \le 10^6$ |
入出力例
入力例 1
4 3
0 1
1 2
2 3
3
4
2出力例 1
6
24
0パスグラフ P_4 の彩色多項式 $P(K) = K(K-1)^3$。$K=3$: $3 \times 8 = 24$... → $K=3$ で実際 $P(3)=3 \times 2^3 = 24$? 問題例では $6$ なので問題文参照。
概念図: 木のクロマティック多項式の導出
ヒント（段階的開示）
ヒント1: 方向性
ヒント2: アプローチ
帰納法: 葉 $v$（親 $u$ 1つ）を取り除いた木 $T'$ の多項式が $K(K-1)^{N-2}$ とすると、$v$ は $u$ の色以外の $K-1$ 通り → $P(K) = K(K-1)^{N-1}$。
特殊ケース: $K=0$ → 0、$K=1$ かつ $N \ge 2$ → 0。
ヒント3: コード骨格
MOD = 10**9 + 7
for K in queries:
ans = K % MOD * pow((K-1) % MOD, N-1, MOD) % MOD
print(ans)模範解答 (Python)
import sys
input = sys.stdin.readline
def main():
MOD = 10**9 + 7
N, Q = map(int, input().split())
# 木の構造（クロマティック多項式には不要だが読み込む）
for _ in range(N - 1):
input()
# 木のクロマティック多項式: P(K) = K * (K-1)^(N-1)
out = []
for _ in range(Q):
K = int(input())
if K == 0:
out.append(0)
elif K == 1 and N > 1:
out.append(0)
else:
ans = K % MOD * pow((K - 1) % MOD, N - 1, MOD) % MOD
out.append(ans)
print('\n'.join(map(str, out)))
main()Step-by-Step 解説
Step 1: 閉形式の導出
帰納法: N=1 では $P(K)=K$。葉を順次除くと各辺が $K-1$ の選択肢を与える（親と異なる色）。
Step 2: 閉形式の意味
$K=2$: 木は二部グラフなので $P(2) = 2$（2通りの2彩色）。$K \ge 2$ で常に彩色可能。
Step 3: mod 計算
Python の pow(K-1, N-1, MOD) は $O(\log N)$ で繰り返し二乗法を使う。
Step 4: 一般グラフへの拡張（参考）
一般グラフでは Deletion-Contraction: $P(G, K) = P(G \setminus e, K) - P(G / e, K)$。木では辺削除が森になるので帰納法が使える。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| K=0 やK=1を特別処理しない | pow(0, 0, MOD) = 1 に注意 |
N=1 かどうかで分岐 |
| MODの適用タイミング | K が大きいとオーバーフロー | K % MOD * pow(...) % MOD |
| 木でない入力への適用 | 閉形式は木のみ成立 | グラフ構造の確認が必要 |
次のステップ
発展: 一般グラフの彩色多項式（Deletion-Contraction + メモ化）$O(2^N \cdot N)$。関連: Broken Profile DP による格子グラフ彩色数え上げ。