We are given a connected graph with $n$ vertices and $n-1$ edges, and a parameter $k$. Each vertex $i$ has a value $c_i \in \{1, 2, \dots, n\}$; these values may repeat. Count the number of connected subgraphs that contain at least one vertex of each value from $1$ to $k$. Here $n\leq10^4$, $k\leq10$. Give the answer modulo $10^9+7$.
I think this graph is a tree. So we can use dynamic program on tree. And $k\leq10$, so we combine that with bitmask. But I can't find the recurrence formula.
Everybody helps me find the recurrence formula, please!
Original Problem (Vietnamese Coastal and Northern Plains Olympiad 2021)
Vietnamese statement: https://drive.google.com/file/d/1zbia22jve9EFB9Y8jH-SZG8m3b8nTi9n/view
Problem 2. SHOPPING MALL
A shopping mall has $n$ kiosks numbered $1$ to $n$, the $i$-th kiosk sells items $c_i$. That shopping mall has $n-1$ two-way street numbered from $1$ to $n-1$, the $k$-th street connects kiosk $u_i$ and kiosk $v_i$.
The system of paths ensures travel between any two kiosks.
During the epidemic period, people want to close some kiosks to easily control buying and selling activities as well as communicating with customers. When a kiosk is shut down, all the roads leading to the kiosk will be blocked for security purposes. In addition, because they do not want to affect customers too much, the supermarket wants to make a plan so that the kiosks are still in operation and must satisfy the following two conditions:
The kiosks still in operation must connect with each other: That is, between any two kiosks that are still open, there must be a path (through unblocked roads).
All items with numbers $1$ through $k$ (essential items) must be available at at least one operating kiosk.
Two plans are said to be different if one kiosk is deactivated in one plan but still in operattion in the other.
Requirements: How many different plans satisfy the above condition?
Data: Input from text file KIOSKS.INP
Line 1 contains 2 positive integers $n \leq 10^4, k \leq 10$
Line 2 contains $n$ positive integers $c_1, c_2, …, c_n (\forall i: c_i \leq n)$
− 1 next lines, the $i$-th line contains two positive integers $u_i$ and $v_i$
Numbers on the same line of input are separated by a space
Result: Write to the text file KIOSKS.OUT a single integer that is the remainder in division: number the solution that satisfying the problem condition for $1000000007 (10^9 + 7)$
There are 3 subtasks:
Subtask 1 (30% of the score): $k = 1$
Subtask 2 (30% of the score): Each kiosk has no more than 2 roads connecting to it.
Subtask 3 (40% score): No additional constraints other than those stated in the assignment.