Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Budget Tour

By ashikurrahman · Limits 3s, 512 MB

Dipu Bhai lives in a country called Chocoland. There are nn cities in Chocoland. The cities are numbered from 11 to nn. The cities of Chocoland can be represented as a tree.

There is a cost associated with every city. It is called the tour cost. Tour cost of ithi^{th} city is denoted by an integer aia_i, means Dipu Bhai has to pay exactly aia_i amount of money to visit the city ii. Dipu Bhai has mm amount of money. He wants to visit the cities of Chocoland. But he has a limited money and can not visit all the cities. So, he is interested in how many city he can visit uu and vv(1u,vn)(1 \le u, v \le n) such that in a simple path from uu to vv he can visit all the cities and the sum of tour cost of all the cities from uu to vv (inclusive uu and vv) does not exceed mm.

In this problem you have to solve for qq independent queries of mm.

Input

The first line contains a single integer nn(2n105)(2 \le n \le 10^5) number of cities in Chocoland.

The next line contains nn space-separated integers a1,a2,,ana_1, a_2, …, a_n (1ai100)(1 \le a_i \le 100) tour cost of the cities. Tour cost of ithi^{th} city is aia_i.

The following n1n - 1 lines contain two space-separated integers uu and vv(1u,vn)(1 \le u, v \le n) describe city uu and city vv are connected by a bidirectional edge.

The next line contains an integer qq (1q10)(1 \le q \le 10) number of queries.

The following qq line contains a single integer mm (1m107)(1 \le m \le 10^7) amount of money Dipu Bhai has.

It is guaranteed that the given edges will form a tree.

Output

For each query print a single integer the number of cities uu and vv (1u,vn)(1 \le u, v \le n) Dipu Bhai can visit spending not more than mm amount of money.

Samples

InputOutput
5
3 2 4 1 9
1 2
1 3
2 4
2 5
3
2
5
7
2
8
12

Chocoland in Sample 1: For m=7m = 7 the valid 1212 pairs of cities are (1,1)(1, 1), (1,2)(1, 2), (1,3)(1, 3), (1,4)(1, 4), (2,1)(2, 1), (2,2)(2, 2), (2,4)(2, 4), (3,1)(3, 1), (3,3)(3, 3), (4,1)(4, 1), (4,2)(4, 2) and (4,4)(4, 4).

InputOutput
8
6 1 8 2 9 5 5 3
1 2
1 3
1 4
2 5
2 6
3 7
7 8
5
1
2
5
10
100
1
2
5
20
64

    Discussion

    Statistics


    100% Solution Ratio

    YouKnowWhoEarliest, 3w ago

    alamkhanFastest, 0.4s

    YouKnowWhoLightest, 14 MB

    NirjhorShortest, 1722B

    Submit

    Login to submit

    Editorial

    There is a well known centroid decomposition problem for finding the number of ‘k’ length path in a ...

    Toph uses cookies. By continuing you agree to our Cookie Policy.