codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/6a3d4d9a4b0794f6c1cce0ebced5fe1e66ad945c.png) 
     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.