All Tracks Algorithms Dynamic Programming Problem

Berland Programming Contests

Algorithms, Dynamic Programming, Tree, bitmask, dynamic programming


The country of Berland consists of N cities, numbered 1 through N. The cities are connected by roads in such a way that there is exactly one way to reach any city from any other city without visiting some city twice. In other words, the road map is represented by a tree.

A company called Suarez runs M different types of programming contests throughout Berland. A programming contest of each type may or may not be held in a particular city; for each city and each contest type, you are given the information if a contest of this type is held in this city.

Now, a person called Phillipe wants to participate in these contests according to the following rules:

  1. Phillipe selects a connected subset of the cities, i.e. a connected subgraph of the tree.

  2. Then, Phillipe determines all types of programming contests such that a contest of that type may be held in every city from the subset chosen in step 1.

  3. He then participates in all programming contests of types chosen in step 2 in all cities of the subset.

The Suarez company has a rule which states that to participate in programming contests of k distinct types, a contestant needs to use a k-pass (it's free though). Even a contestant that doesn't participate in any programming contest needs to use a 0-pass.

Phillipe performs the procedure described above for each connected subset of Berlandian cities independently. You need to find the number of k-passes he will buy modulo \(10^9+7\), for each possible k.


  • \( 1 \le T \le 5 \)

  • \( 1 \le N \le 5,000 \)

  • \( 1 \le M \le 10 \)

  • the input graph will be a tree

Input format

The first line of the input contains a single integer T denoting the number of test cases in one test file.

The first line of each test case contains two space-separated integers N and M.

Each of the next \( N - 1 \) lines contains two space-separated integers u and v, denoting an edge between vertices u and v.

Each of the next N lines contains M space-separated integers. The j-th integer on the i-th of these lines is 1 if a programming contest of type j is held in city i or 0 if it is not held in city i.

Output format

For each test case, print a single line containing \( M+1 \) space-separated integers. For each \(0 \le k \le M\), the k-th of these integers should denote the number of k-passes Phillipe will buy, modulo \( 10^9+7 \).

3 2
1 2
1 3
1 0
1 1
0 1
2 3 1

The connected subgraphs are:

  1. 1, contest types: 1, pass type: 1

  2. 2, contest types: \( \{ 1,2 \} \), pass type: 2

  3. 3, contest types: 2, pass type: 1

  4. \( \{ 1,2 \} \), contest types: 1, pass type: 1

  5. \( \{ 1,3 \} \), contest types: \(\emptyset\), pass type: 0

  6. \( \{ 1,2,3 \} \), contest types: \(\emptyset\), pass type: 0

Hence, the answer is \( [2,3,1] \).

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications