CF1139C.Edgy Trees

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given a tree (a connected undirected graph without cycles) of nn vertices. Each of the n1n - 1 edges of the tree is colored in either black or red.

You are also given an integer kk . Consider sequences of kk vertices. Let's call a sequence [a1,a2,,ak][a_1, a_2, \ldots, a_k] good if it satisfies the following criterion:

  • We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from a1a_1 and ending at aka_k .
  • Start at a1a_1 , then go to a2a_2 using the shortest path between a1a_1 and a2a_2 , then go to a3a_3 in a similar way, and so on, until you travel the shortest path between ak1a_{k-1} and aka_k .
  • If you walked over at least one black edge during this process, then the sequence is good.

Consider the tree on the picture. If k=3k=3 then the following sequences are good: [1,4,7][1, 4, 7] , [5,5,3][5, 5, 3] and [2,3,7][2, 3, 7] . The following sequences are not good: [1,4,6][1, 4, 6] , [5,5,5][5, 5, 5] , [3,7,3][3, 7, 3] .

There are nkn^k sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo 109+710^9+7 .

输入格式

The first line contains two integers nn and kk ( 2n1052 \le n \le 10^5 , 2k1002 \le k \le 100 ), the size of the tree and the length of the vertex sequence.

Each of the next n1n - 1 lines contains three integers uiu_i , viv_i and xix_i ( 1ui,vin1 \le u_i, v_i \le n , xi{0,1}x_i \in \{0, 1\} ), where uiu_i and viv_i denote the endpoints of the corresponding edge and xix_i is the color of this edge ( 00 denotes red edge and 11 denotes black edge).

输出格式

Print the number of good sequences modulo 109+710^9 + 7 .

输入输出样例

  • 输入#1

    4 4
    1 2 1
    2 3 1
    3 4 1
    

    输出#1

    252
  • 输入#2

    4 6
    1 2 0
    1 3 0
    1 4 0
    

    输出#2

    0
  • 输入#3

    3 5
    1 2 1
    2 3 0
    

    输出#3

    210

说明/提示

In the first example, all sequences ( 444^4 ) of length 44 except the following are good:

  • [1,1,1,1][1, 1, 1, 1]
  • [2,2,2,2][2, 2, 2, 2]
  • [3,3,3,3][3, 3, 3, 3]
  • [4,4,4,4][4, 4, 4, 4]

In the second example, all edges are red, hence there aren't any good sequences.

首页