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

闲话：希望明天 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)

算。

CPP

#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;
}

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

文章操作

相关推荐

评论

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