P6668 [Tsinghua Training 2016] Connected Subtrees

Xiao D, a “Little M supremacist”, is in a very good mood today and plans to prepare a Christmas gift for Xiao M. He bought a Christmas tree. This Christmas tree is a tree with $n$ nodes, and node $i$ has a color $c_i$. Xiao D thinks it would not look good if some color appears too many times, so at most $5$ nodes have the same color. Xiao M is very happy to receive the gift, but she has recently become interested in counting problems, so she has some questions for Xiao D to solve. Each time, Xiao M cares about three different colors $a,b,c$. She wants to know how many different non-empty connected subgraphs of this Christmas tree satisfy that the numbers of nodes with colors $a,b,c$ inside are respectively $na,nb,nc$. Since the number may be very large, you only need to output the remainder modulo $10^9+7$. Xiao D can of course solve this problem easily. Although you have been fed “dog food”, you also want to train your skills. Can you solve this problem?

The first line contains two integers $n$ and $Q$, denoting the size of the tree and the number of queries. The second line contains $n$ integers, where the $i$-th integer is $c_i$, the color of the $i$-th node. The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is an edge between node $a$ and node $b$. The next $Q$ lines each contain $6$ integers $a,na,b,nb,c,nc$, describing a query as stated in the problem.

For each query, output one line containing the answer.

#### Limits and Conventions $1≤i≤n$, $1≤c_i≤n$. For each query: $0≤na,nb,nc≤5$, $1≤a,b,c≤n$, and $a,b,c$ are pairwise distinct. For $10\%$ of the queries, $n,Q≤10$. For another $10\%$ of the queries, $n≤15$, $Q≤50$. For another $10\%$ of the queries, $n,Q≤1000$. For another $5\%$ of the queries, $n,Q≤50000$, and if the input tree is rooted at node $1$, the maximum depth is at most $35$ (the depth of node $1$ is $0$). For another $5\%$ of the queries, $n,Q≤100000$, and if the input tree is rooted at node $1$, the maximum depth is at most $35$ (the depth of node $1$ is $0$). For another $20\%$ of the queries, $n,Q≤100000$, and the sum over all queries of $(na+1)^2(nb+1)^2(nc+1)^2$ is at most $10^8$. For another $40\%$ of the queries, $n,Q≤100000$, and the sum over all queries of $(na+1)(nb+1)(nc+1)$ is at most $8\times 10^6$. Translated by ChatGPT 5