首页 > 试题广场 >

树

[编程题]树
  • 热度指数：34 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。

输入描述:
第一行两个整数n，k代表点数和颜色数；
接下来n-1行，每行两个整数x,y表示x与y之间存在一条边；


输出描述:
输出一个整数表示方案数（mod 1e9+7）。
示例1

输入

4 3
1 2
2 3
2 4

输出

39

备注:
对于30%的数据，n≤10, k≤3；
对于100%的数据，n,k≤300。
算法知识视频讲解
开通博客
头像 LB_tq
发表于 2020-04-06 12:59:08
Solution 其实是道数论题。 题意可以转化为将树分割为不超过 个连通块，每个连通块颜色不同。若将树分割为 个连通块，则需要删去 条边，故方案数为 。同时，要从 种颜色中选出 中颜色染色，而且是有顺序的，故方案数为 。 综上，总的方案数为： 可以线性求逆元，枚举 实现。 时间复杂 展开全文
去ta的博客 赞 (24) 回复(1) 收起
头像 shyyhs
发表于 2020-04-06 19:07:38
题目意思是用k个点把一个有n个节点的树染色,然后的地方必须联通,求有多少方案数?下面给大家介绍两种做法..做法1:切边表示染色用的颜色个数,比如我要用3种颜色染色,那么我就只要考虑切2条边,比如切2-4,和3和7这是一种方案,那么,考虑树,一共n个点,一共n-1条边,我可以用k种颜色染色,那么就是切 展开全文
去ta的博客 赞 (10) 回复(2) 收起
头像 O__0
发表于 2020-04-06 10:52:36
首先思考一下，题目需要你将一棵树分成若干个连通块，连通块上的颜色相同，不同连通块之间的颜色不同。然后数据范围很小，考虑树上dp，dp[i][j] 表示第 i 个节点为根的子树分成 j 个连通块的方案数。 然后我就不会了，但是仔细一想，把一棵树分成两个连通块不就是删除一条边，那分成 x 个连通块不就是 展开全文
去ta的博客 赞 (8) 回复(3) 收起
头像 Kur1su
发表于 2020-04-06 14:57:54
Solution Code #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long long LL; const int N = 1 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 三金老师
发表于 2020-04-06 10:42:44
Solution因为是树，所以保证任意两点都可以到达，所以可以选择从一个叶子节点作为出发点思考， 表示这个叶子节点所在包含了 i 个节点的子图染了 j 种颜色的方案。考虑当前取的颜色是否和前 次取的颜色一样，就是两种决策： 若取的颜色相同则： 若取的是新的颜色,则有 种新颜色可以选择，则： 展开全文
去ta的博客 赞 (4) 回复(1) 收起
头像 一只橘橘猫
发表于 2020-04-06 14:42:15
题意：给出一颗树，有个节点，用种不同的颜色给每个节点染色，要求保证所有相同颜色的节点都相邻 设计知识点：排列组合 解法：首先，题意可以理解为将其分成 个联通分量的染色方案数之和，将一棵树拆分成 i 个联通分量需要砍掉条边，就相当于从条边选择条边，那么方案数就是,接下来就可以从个颜色中选择种颜色， 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Alan233
发表于 2020-04-10 16:01:56
树 题目链接：牛客13611 树 Description 给定一颗有 个节点的树，有 种颜料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对 ，满足到的路径上所有点的颜色相同（包括和）。统计方案数，答案对取模。数据范围 Solution 这是一道结论题。如果直接做，显然不好做， 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 wxyww
发表于 2020-04-06 11:08:46
solution 仔细思考一下题意，发现其实就是要求将树分成不超过K个连通块，然后给每个连通块分配一种颜色。 假设连通块个数为x，那么根据乘法原理，给每个连通块分配不同颜色的方案数就是 然后问题就只剩下了如何求将树分成不超过K个连通块的方案数。 这显然可以用树形dp来求。 用f[u][i]表示将u这 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 get_right_Lkl
发表于 2020-04-06 13:43:16
题目大意 shy有一颗树，树有n个结点。有k种不同颜色的染料给树染色。一个染色方案是合法的，当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同。请统计方案数。 解答 千万不要被树迷惑了，仔细一想，这和树有什么关系呢？可以转换一下思路：题目的意思就是最多切k-1条边 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 塞蒙尘
发表于 2020-04-06 19:29:41
statement 将n个点的树分成不超过k个连通块，并分别上色，统计方案数。 solution 设为将点u的子树分成i个连通块的方案数。考虑如何将子树v的结果合并到u，那么有： 其中第一条式子表示，原子树u分成i个连通块，子树v分成j个连通块，合并后u和v属于同一连通块的方案数。第二条式子表示，原 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

组合数学 树
上传者：牛客301599号
难度：
3条回答 4372浏览

热门推荐

通过挑战的用户

相关试题

树

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号