Berland Programming Contests
Tag(s):

## Algorithms, Dynamic Programming, Medium, Tree, bitmask, dynamic programming

Problem
Editorial
Analytics

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.

Constraints

• $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$.

SAMPLE INPUT
1
3 2
1 2
1 3
1 0
1 1
0 1
SAMPLE OUTPUT
2 3 1
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

December Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Algorithms > Searching
• Data Structures > Arrays
• Math > Combinatorics