All submissions for this problem are available.
You are given a tree with N nodes and N-1 edges. We define a region as a set of nodes, such that if we remove all other nodes from the tree, these nodes still remain connected i.e. there exists a path between any two remaining nodes.
All the nodes have a weight associated to them. You are given Q queries. Each query has a number k. You have to find number of regions, such that the minimum weight among all the nodes of that region is exactly k. Output your answer modulo 10^9 + 7.
The first line will contain N, the number of nodes. Next line will contain N integers. The ith integer will indicate weight, the weight of ith node. Next N-1 lines will contain 2 integers "x y" (quotes for clarity) denoting an edge between node x and node y. Next line will contain a number Q , the number of queries. Next Q lines will contain an integer k , which is as described in problem statement.
NOTE:nodes are numbered 1 indexed
You have to output Q lines, each containing a single integer, the answer to the corresponding query.
- 1 ≤ N ≤ 1500
- 1 ≤ x,y ≤ n
- 1 ≤ Q ≤ 2000
- 1 ≤ weight ≤ 10^9
Input: 4 2 4 3 1 4 3 4 2 4 1 4 1 2 3 4 Output: 8 1 1 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.