P3914 Coloring Count

There is a tree with $N$ nodes, numbered $1, 2, \cdots, N$. You need to color it so that adjacent nodes have different colors. There are $M$ colors, numbered $1, 2, \cdots, M$. Each node may be colored with a subset of the $M$ colors. Compute the number of different valid colorings modulo $10^9 + 7$.

The first line contains two integers $N, M$. Then follow $N$ lines. The $i$-th line describes the colors allowed for node $i$: the first integer $k_i$ is the number of allowed colors, followed by $k_i$ integers giving the allowed color indices. Finally, the last $N - 1$ lines each contain two integers $A_i, B_i$, indicating an edge $(A_i, B_i)$.

Output one integer, the number of valid colorings modulo $10^9 + 7$.

• For 30% of the testdata, $1 \le N \le 10; 1 \le M \le 4$. • For 60% of the testdata, $1 \le N \le 200; 1 \le M \le 200$. • For 100% of the testdata, $1 \le N \le 5000; 1 \le M \le 5000$. Translated by ChatGPT 5