首页 > 试题广场 >

“好序列”的个数

[编程题]“好序列”的个数
  • 热度指数：462 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
现在你面前有一棵n个节点的树（全连通无环图）。树上的边只有2种颜色，红色或者黑色。现在还给你一个整数k，考虑下面这个k个节点的序列[a1, a2, ..., ak]。
[a1, a2, ..., ak]如果是”好序列“当且仅当满足下面的条件：
1. 我们要走一条从a1开始到ak结束的路径。
2. 从a1开始，到a2走一条a1到a2的最短路。然后从a2开始，继续走一条到a3的最短路，以此类推，最终到a(k-1)和ak。
3. 走的路径中至少包含一条黑色的边。

我们看一下上面的图片中的树，如果k=3，那么下面的序列是“好序列”：[1,4,7], [5,5,3]。下面的序列不是好序列： [1,4,6], [5,5,5], [3,7,3]。
总共有n^k（n的k次方种路径方案），那么有多少路径是“好序列”呢？这个值可能非常大，输出的结果对(10^9+7)取模就可以。

输入描述:
第一行是2个整数n和k，其中(2 <= n <= 10^5, 2 <= k <= 100)，n表示树的节点个数，k表示序列的长度。

下面n-1行，每行包含3个整数，u[i], v[i], w[i]，其中1 <= u[i], v[i] <= n, w[i] = 0或1。u[i], v[i]表示这两个节点之间有一条边，w[i]表示这条边的颜色，其中0表示红色，1表示黑色。


输出描述:
输出所有“好序列”的个数模(10^9+7)
示例1

输入

4 4
1 2 1
2 3 1
3 4 1

输出

252

说明

这个例子中，所有序列一共有4^4 = 256个，其中不是好序列的只有4个：

[1, 1, 1, 1]

[2, 2, 2, 2]

[3, 3, 3, 3]

[4, 4, 4, 4]
示例2

输入

4 6
1 2 0
1 3 0
1 4 0

输出

0
示例3

输入

3 5
1 2 1
2 3 0

输出

210
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 快手 2020 Java工程师
上传者：小小
难度：
4条回答 5181浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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