# 牛客多校 2018 第三场 G Coloring Tree（搜索+思维）

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

### 题解

1->2->3

1有两种染色方案，3也有两种染色方案，这样一看，2就没有染色方案了，最后乘出来的答案就会为0。这是为什么呢？

### 代码

G答案正确788991801936
#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(dis, 0, sizeof(dis));
tot = 0;
}

{
edge[tot].to = v;
}

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);