1139C.md (2282B)
1 Source: https://codeforces.com/problemset/problem/1139/C 2 3 C. Edgy Trees 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a tree (a connected undirected graph without cycles) of $n$ vertices. Each of the $n - 1$ edges of the tree is colored in either black or red. 22 23 You are also given an integer $k$. Consider sequences of $k$ vertices. Let's call a sequence $[a_1, a_2, \ldots, a_k]$ good if it satisfies the following criterion: 24 25 * We will walk a path (possibly visiting same edge/vertex multiple times) on the tree, starting from $a_1$ and ending at $a_k$. 26 * Start at $a_1$, then go to $a_2$ using the shortest path between $a_1$ and $a_2$, then go to $a_3$ in a similar way, and so on, until you travel the shortest path between $a_{k-1}$ and $a_k$. 27 * If you walked over at least one black edge during this process, then the sequence is good. 28 29  30 31 Consider the tree on the picture. If $k=3$ then the following sequences are good: $[1, 4, 7]$, $[5, 5, 3]$ and $[2, 3, 7]$. The following sequences are not good: $[1, 4, 6]$, $[5, 5, 5]$, $[3, 7, 3]$. 32 33 There are $n^k$ sequences of vertices, count how many of them are good. Since this number can be quite large, print it modulo $10^9+7$. 34 35 Input 36 37 The first line contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $2 \le k \le 100$), the size of the tree and the length of the vertex sequence. 38 39 Each of the next $n - 1$ lines contains three integers $u_i$, $v_i$ and $x_i$ ($1 \le u_i, v_i \le n$, $x_i \in \{0, 1\}$), where $u_i$ and $v_i$ denote the endpoints of the corresponding edge and $x_i$ is the color of this edge ($0$ denotes red edge and $1$ denotes black edge). 40 41 Output 42 43 Print the number of good sequences modulo $10^9 + 7$. 44 45 Examples 46 47 Input 48 49 ``` 50 4 4 51 1 2 1 52 2 3 1 53 3 4 1 54 ``` 55 56 Output 57 58 ``` 59 252 60 ``` 61 62 Input 63 64 ``` 65 4 6 66 1 2 0 67 1 3 0 68 1 4 0 69 ``` 70 71 Output 72 73 ``` 74 0 75 ``` 76 77 Input 78 79 ``` 80 3 5 81 1 2 1 82 2 3 0 83 ``` 84 85 Output 86 87 ``` 88 210 89 ``` 90 91 Note 92 93 In the first example, all sequences ($4^4$) of length $4$ except the following are good: 94 95 * $[1, 1, 1, 1]$ 96 * $[2, 2, 2, 2]$ 97 * $[3, 3, 3, 3]$ 98 * $[4, 4, 4, 4]$ 99 100 In the second example, all edges are red, hence there aren't any good sequences.