NC17246. G、Coloring Tree
描述
输入描述
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.
示例1
输入:
2 1 1 1 2
输出:
1
示例2
输入:
4 3 2 1 2 2 3 3 4
输出:
18
示例3
输入:
4 3 2 1 2 1 3 1 4
输出:
24
C++14(g++5.4) 解法, 执行用时: 557ms, 内存消耗: 1044K, 提交时间: 2018-07-27 13:00:32
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
vector<int> v[N];
const int P=1e9+7;
int n,m,D,cox,coy,vis[N],q[N],h,t,x,y,ans1,ans2;
void dfs(int x,int fx,int d){
if(vis[x]){if(d<D)cox--;if(d<=D)coy--;}
for(auto y:v[x])if(y^fx)dfs(y,x,d+1);
}
int main(){
scanf("%d%d%d",&n,&m,&D);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y); v[y].push_back(x);
}ans1=ans2=1;
for(q[t++]=1;h^t;){
cox=coy=m;
dfs(x=q[h++],0,0);
ans1=1LL*ans1*cox%P;
ans2=1LL*ans2*coy%P;
for(auto y:v[x])if(!vis[y])q[t++]=y;
vis[x]=1;
}
printf("%d\n",(ans1-ans2+P)%P);
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 657ms, 内存消耗: 976K, 提交时间: 2020-02-28 14:05:53
#include<bits/stdc++.h>
using namespace std;
int n,m,k,a=1,b=1,h,t,u,x,y,M=1e9+7;
vector<int> e[5001];
int c[5001],q[5001];
void f(int u,int w,int d)
{
if(c[u])
{
if(d<k) x--;
if(d<=k) y--;
}
for(int&v:e[u])
if(v^w) f(v,u,d+1);
}
int main()
{
cin>>n>>m>>k;
while(--n)
{
cin>>x>>y;
e[x].push_back(y),e[y].push_back(x);
}
for(q[t++]=1;h^t;)
{
x=y=m;
f(u=q[h++],0,0);
a=1ll*x*a%M;
b=1ll*y*b%M;
c[u]=1;
for(int&v:e[u])
if(!c[v]) q[t++]=v;
}
cout<<(a-b+M)%M;
}