Coloring Tree
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 262144K，其他语言524288K
- 64bit IO Format: %lld
题目描述
Christmas is coming! Eddy has received a Christmas tree as gift. Not surprisingly, the tree consists of N vertices and N-1 edges and magically remains connected. Currently, all the vertex of the tree is uncolored. Eddy wants to color each vertex into one of K colors. However, there are too many way to color the tree(i.e. KN ways). Eddy doesn't want the result of coloring being too boring. Thus, he defines the colorness of a tree as follow:
The colorness of a tree is the minimum distance between two vertex colored in the same color.
Now, Eddy is wondering how many way to color the tree such that the colorness of the tree will be D.
输入描述:
The first line of input contains three space-separated integer N, K, D indicating the number of vertices, number of colors, and the required colorness.
For each following N-1 lines, each contains two space-separated positive integer ui, vi indicating that there's an edge between ui and vi.
1 ≤ K < N ≤ 5000
1 ≤ D ≤ N
1 ≤ ui < vi ≤ N
It's guaranteed that the given input is a tree.输出描述:
Output one line contains an integer indicating the number of way module 1000000007(109+7) to color the tree resulting in colorness being D.输入
2 1 1
1 2输出
1输入
4 3 2
1 2
2 3
3 4输出
18输入
4 3 2
1 2
1 3
1 4输出
24链接
https://www.nowcoder.com/acm/contest/141/G
题意
有一棵n个节点n-1条边的树，有k种不同颜色的染料，可以对每个结点进行染色。现定义一棵树的colorness为染了同种颜色的两个结点的最小距离。问colorness为d的染色方案数量。
题解
简单一点讲，就是转化为colorness>=d的方案数减去colorness>=d+1的方案数，colorness>=d即距离小于d的两个结点不能染相同的颜色。具体分析参考xseventh的题解：传送门。
给你一棵树，你可以对树进行染色，树的价值定义为最小的相同颜色的节点之间的距离，问你当树的价值为d的时候，有多少种染色方案。我们可以转化一下题目，可以转变成当树的价值>=d时，有多少种方案，然后我们用>=d的方案数减去>=d+1的方案数 就是价值刚好为d的方案数了。
怎么求树的价值>=d的方案数呢？这里可以看成对于任意一个节点，所有和它距离小于d的节点，不能和它有相同的颜色。
然后我们随便找个根节点开始bfs染色，怎么染色呢？
我们考虑根节点，它有k种颜色可以染，我们给根染了一种颜色之后，所有和根在距离<d的点，可以被染的颜色都会少一种，然后我们bfs对所有的节点都这样做，然后我们最后把每个点可以染的颜色种类数乘起来，就是我们需要的答案了。
上述思路代码实现应该是很简单的，因为数据范围只有5000，我们可以对每个点都dfs一次，求出所有点之间的距离。然后计算的时候每次都把距离<d的所有点可选颜色都-1。
代码实现不是主要部分，重点是为什么按照bfs的顺序去做可以保证答案正确呢？
这里就要考虑一个问题了。假如我们有两种颜色，每个节点不能和距离<=1的点有相同的颜色，我们要怎么做呢？
比如我们有三个节点
1->2->3
如果我们不按照bfs顺序来染色
1有两种染色方案，3也有两种染色方案，这样一看，2就没有染色方案了，最后乘出来的答案就会为0。这是为什么呢？
我们发现1和3可以选取的颜色有重复，然后作用到2这个节点就会出问题。
那么 为什么bfs能保证答案正确呢？
我画了很久的图。。发现了一个性质。。
如果我们按照bfs的顺序来选择颜色计算方案数的话，已经选过颜色的和当前节点距离在d以内的节点，一定两两距离都在d以内，就是说，当前节点距离d以内的已经选择过颜色的节点在选择颜色种类的时候一定会互相考虑到彼此节点，如果我们用dfs，就保证不了这个性质了。
代码
| 题号 | 运行结果 | 运行时间(ms) | 使用内存(KB) | 代码长度 |
|---|---|---|---|---|
| G | 答案正确 | 788 | 99180 | 1936 |
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 5010;
const int mod = 1000000007;
typedef long long ll;
int head[maxn], tot, n, k, d;
int dis[maxn][maxn];
ll color[maxn];
bool vis[maxn];
struct Edge
{
int to, next;
}edge[maxn << 2];
void init()
{
memset(head, -1, sizeof(head));
memset(dis, 0, sizeof(dis));
tot = 0;
}
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int s, int u, int pre) // s到其他点的距离
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (v == pre)
continue;
dis[s][v] = dis[s][u] + 1;
dfs(s, v, u);
}
}
ll solve(int d)
{
memset(vis, 0, sizeof(vis));
queue <int> Q;
Q.push(1);
for (int i = 1; i <= n; ++i) // 初始化每个点可以染k种颜色
color[i] = k;
ll ans = 1;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 1; i <= n; ++i)
{
if (vis[i] && dis[u][i] < d) // 已访问且距离小于d那么剩余可以染的颜色减减
color[u]--;
}
if (color[u] <= 0) // 已经没有可以染的颜色
return 0;
vis[u] = true;
ans = ans * color[u] % mod; // 记录总的方案树
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (!vis[v])
Q.push(v);
}
}
return ans;
}
int main()
{
int u, v;
while (scanf("%d%d%d", &n, &k, &d) != EOF)
{
init();
for (int i = 1; i < n; ++i)
{
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
for (int i = 1; i <= n; ++i) // 任意两点距离
dfs(i, i, -1);
ll ans = (solve(d) - solve(d + 1) + mod) % mod; // 距离大于等于d的方案减去大于等于d+1的方案
printf("%lld\n", ans);
}
return 0;
}The end.
2018-08-07 星期二