题解：P13484 [GCJ 2008 EMEA SemiFinal] Rainbow Trees

Conan15 · 2025-10-31 15:48:43 · 题解

闲话：希望明天 CSP 会出这种简单而有趣的数数题。

先简化问题：考虑如果只有相邻边不相同的限制，怎么求方案数。\ 事实上是简单的，假设以 1 为根，从上往下确定边的颜色。对于一个点 u，它和它父亲的连边颜色已经确定，现在确定它和它儿子的连边。\ 注意我们只要求颜色不相同，所以没有必要记录颜色是什么。所以设 deg_u 表示 u 的度数，则有 A^{k-1}_{deg_u-1} 种确定方法。\ 根据乘法原理相乘即可。

考虑距离为 3 的路径也互不相同怎么做，凭直觉枚举中间的那条边（下图中的红边），设它周围（包括它）总共有 t 条边，其中有 a 条边已经确定颜色。

初始的时候随便找一条边作为红边，假设红边已经确定颜色（a=1），那么有 A^{k-a}_{t-a} 种填法确定这 t-a 条边。\ 现在考虑从红边转移到蓝边，不难推出 t 和 a 的变化情况，填法还是 A^{k-a}_{t-a}。\ 根据乘法原理相乘即可，最后记得 \times k 因为第一条红边可以任意选。

时间复杂度 O(Cn^2)，因为排列数需要 O(n) 算。

#include <bits/stdc++.h>
using namespace std;
const int N = 505, M = N << 1, mod = 1e9 + 9;
int T, n, k, h[N], e[M], ne[M], idx;
int X, Y, deg[N];
inline void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

int A(int n, int m) {
    long long res = 1; for (int i = n - m + 1; i <= n; i++) (res *= i) %= mod;
    return res;
}

long long ans;
void dfs(int x, int y, int t, int a) {
    (ans *= A(k - a, t - a)) %= mod;
    if (deg[y] == 1) return;
    for (int i = h[y]; ~i; i = ne[i]) {
        int v = e[i]; if (v == x) continue;
        dfs(y, v, deg[y] + deg[v] - 1, deg[y]);
    }
}

void solve(int id) {
    scanf("%d%d", &n, &k), ans = 1;
    for (int i = 1; i <= n; i++) h[i] = -1, deg[i] = 0; idx = 0;
    for (int i = 1, a, b; i < n; i++) scanf("%d%d", &a, &b), add(a, b), add(b, a), deg[a]++, deg[b]++;
    for (int i = 1; i <= n; i++) if (deg[i] == 1) { X = i; break; }
    for (int i = h[X]; ~i; i = ne[i]) Y = e[i];
    dfs(X, Y, deg[Y], 1);
    (ans *= k) %= mod;
    printf("Case #%d: %lld\n", id, ans);
}

int main() {
    scanf("%d", &T);
    for (int id = 1; id <= T; id++) solve(id);
    return 0;
}