牛客网暑期ACM多校训练营(第三场)G:Coloring Tree(函数的思想)
之前两次遇到过函数的思想的题,所以这次很敏感就看出来了。可以参考之前的题:
https://www.cnblogs.com/hua-dong/p/9291507.html
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.
题意:用K种颜色给树染色,问有多少种染色方案,使得min{同色间距离}=D。
思路:一眼题,但是当时没时间了,4点就出门了。晚上一会就补了,emmm。
还是函数的思想,令F(X)表示距离在X内的点都不同色。那么只要在搜索的同时(BFS或者DFS都可以)染色即可。
如果对S点染色,在X范围内的有Y个点染色了,那么S点的染色种类数为K-Y,回去搜索一下已经染过色的有多少就行了,复杂度为O(N^2)。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Mod=1e9+,maxn=;
int Next[maxn],Laxt[maxn],To[maxn],cnt;
int K,q[maxn],col[maxn],head,tail,ans;
void add(int u,int v){ Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; }
int dfs(int u,int f,int dis){
int res=;
for(int i=Laxt[u];i;i=Next[i])
if(To[i]!=f&&col[To[i]]&&dis>) res+=dfs(To[i],u,dis-);
return res;
}
int cal(int D)
{
int res=; memset(col,,sizeof(col)); head=tail=;
q[++head]=;
while(tail<head){
int u=q[++tail]; col[u]=;
int num=dfs(u,,D);
res=(ll)res*(K+-num)%Mod;
for(int i=Laxt[u];i;i=Next[i]) if(!col[To[i]]) q[++head]=To[i];
}
return res;
}
int main()
{
int N,D,u,v,i;
while(~scanf("%d%d%d",&N,&K,&D)){
cnt=; ans=; head=; tail=;
memset(Laxt,,sizeof(Laxt));
for(i=;i<N;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
printf("%d\n",(cal(D-)-cal(D)+Mod)%Mod);
}
return ;
}
最新文章
- Unity小游戏制作 - 暗影随行
- JS实战 &#183; 级联菜单选择省份和城市(两种)
- javascript中异步和闭包产生的困惑
- Django1.9开发博客(11)- 富文本与代码高亮
- jar MANIFEST.MF 汇总
- struts配置测试中遇到报错信息,记录下
- H5网页播放器播不了服务器上的mp4视频文件
- MSP430F149学习之路——时钟1
- EasyUI中datagrid的行编辑模式中,找到特定的Editor,并为其添加事件
- smarty半小时快速上手教程(转)
- USACO The Tamworth Two 模拟
- css选择器的优先级别
- $.when()方法翻译
- JavaScript addEventListener 第三个参数
- 将php项目打包docker镜像
- java 网络编程之UDP通信和简单的群聊程序
- SAP MM &#39;独立/集中&#39;等于1的MTS物料MRP运行后合并需求触发PR
- laravel 预加载特定的列
- java script基本数据类型与数组
- java 的重写(覆盖) 和重载的区别