AT_joi2026final_e JOI ツアー 2 (JOI Tour 2)

There are $ N $ towns in the country of JOI, numbered from $ 1 $ to $ N $ . Also, there are $ N-1 $ roads in the country of JOI, numbered from $ 1 $ to $ N-1 $ . Road $ j $ ( $ 1 \leq j \leq N-1 $ ) connects town $ U_j $ and town $ V_j $ in both directions. It is possible to travel from any town to any other town by using some number of roads. There is one shop in each town in the country of JOI. In the shop in town $ i $ ( $ 1 \leq i \leq N $ ), a souvenir is sold for price $ A_i $ . This year, $ M $ tours are planned in the country of JOI. The $ k $ -th tour ( $ 1 \leq k \leq M $ ) starts from town $ S_k $ and travels by roads to town $ T_k $ without visiting the same town twice. Note that the $ k $ -th tour visits both towns $ S_k $ and $ T_k $ . It is guaranteed that $ S_k \neq T_k $ . Note that, from the structure of the country of JOI, the sequence of towns visited by a tour is uniquely determined. You are planning to participate in one of these tours and buy one souvenir in each of exactly two of the towns visited on the tour. Moreover, you want to use up exactly the entire budget prepared for souvenirs, so for each of $ Q $ candidate budgets, you decided to investigate in how many ways this can be done. Given the roads in the country of JOI, the prices of the souvenirs, the information on the tours, and the candidate budgets $ B_1, B_2, \ldots, B_Q $ , write a program that computes the number of ways to choose a tour and the towns in which to buy souvenirs. More formally, for each $ q $ ( $ 1 \leq q \leq Q $ ), write a program that computes the number of triples of integers $ (k,u,v) $ satisfying all of the following conditions. - $ 1\leq k\leq M $ . - $ 1\leq u < v \leq N $ . - The $ k $ -th tour visits towns $ u $ and $ v $ . - $ A_u+A_v=B_q $ . ---

Read the following data from the standard input. > $ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $ $ M $ $ S_1 $ $ T_1 $ $ S_2 $ $ T_2 $ $ \vdots $ $ S_M $ $ T_M $ $ Q $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_Q $

Write $ Q $ lines to the standard output. The $ q $ -th line ( $ 1\leq q\leq Q $ ) should contain the number of ways to choose a tour and the towns in which to buy souvenirs so that the budget $ B_q $ is used up exactly. ---

### Subtasks 1. ( $ 3 $ points) $ N\leq 100 $ , $ M\leq 100 $ , $ Q\leq 100 $ . 2. ( $ 4 $ points) $ N\leq 5\,000 $ , $ U_j=j $ ( $ 1\leq j\leq N-1 $ ), $ V_j=j+1 $ ( $ 1\leq j\leq N-1 $ ). 3. ( $ 5 $ points) $ N\leq 5\,000 $ . 4. ( $ 6 $ points) $ Q= 1 $ , $ U_j=j $ ( $ 1\leq j\leq N-1 $ ), $ V_j=j+1 $ ( $ 1\leq j\leq N-1 $ ). 5. ( $ 10 $ points) $ Q= 1 $ . 6. ( $ 7 $ points) $ M\leq 1000 $ , $ U_j=j $ ( $ 1\leq j\leq N-1 $ ), $ V_j=j+1 $ ( $ 1\leq j\leq N-1 $ ). 7. ( $ 12 $ points) $ M\leq 1000 $ . 8. ( $ 10 $ points) $ N\leq 50\,000 $ , $ M\leq 50\,000 $ , $ U_j=j $ ( $ 1\leq j\leq N-1 $ ), $ V_j=j+1 $ ( $ 1\leq j\leq N-1 $ ). 9. ( $ 15 $ points) $ N\leq 50\,000 $ , $ M\leq 50\,000 $ . 10. ( $ 11 $ points) $ U_j=j $ ( $ 1\leq j\leq N-1 $ ), $ V_j=j+1 $ ( $ 1\leq j\leq N-1 $ ). 11. ( $ 17 $ points) No additional constraints. --- ### Sample Explanation 1 First, the towns visited by each tour are as follows. - The $ 1 $ st tour visits towns $ 1, 2, 3, 4 $ . - The $ 2 $ nd tour visits towns $ 1, 6 $ . - The $ 3 $ rd tour visits towns $ 2, 5 $ . - The $ 4 $ th tour visits towns $ 3, 7, 8 $ . Represent a method of participating in the $ k $ -th tour and buying souvenirs in towns $ u $ and $ v $ by $ (k,u,v) $ . Then, for each candidate budget, the ways to use up the budget exactly are as follows. - There are $ 0 $ ways to use up budget $ 1 $ . - There are $ 0 $ ways to use up budget $ 2 $ . - There are $ 4 $ ways to use up budget $ 3 $ : $ (1,1,2) $ , $ (1,1,4) $ , $ (2,1,6) $ , $ (3,2,5) $ . - There are $ 2 $ ways to use up budget $ 4 $ : $ (1,1,3) $ , $ (1,2,4) $ . - There are $ 4 $ ways to use up budget $ 5 $ : $ (1,2,3) $ , $ (1,3,4) $ , $ (4,3,8) $ , $ (4,7,8) $ . - There is $ 1 $ way to use up budget $ 6 $ : $ (4,3,7) $ . - There are $ 0 $ ways to use up budget $ 16 $ . This input example satisfies the constraints of subtasks $ 1, 3, 7, 9, 11 $ . --- ### Sample Explanation 2 This input example satisfies the constraints of subtasks $ 1, 2, 3, 6, 7, 8, 9, 10, 11 $ . ### Constraints - $ 2 \leq N \leq 100\,000 $ . - $ 1\leq A_i\leq N $ ( $ 1 \leq i \leq N $ ). - $ 1\leq U_j\leq N $ ( $ 1 \leq j \leq N-1 $ ). - $ 1\leq V_j\leq N $ ( $ 1 \leq j \leq N-1 $ ). - It is possible to travel from any town to any other town by using some number of roads. - $ 1\leq M \leq 200\,000 $ . - $ 1\leq S_k\leq N $ ( $ 1\leq k\leq M $ ). - $ 1\leq T_k\leq N $ ( $ 1\leq k\leq M $ ). - $ S_k\neq T_k $ ( $ 1\leq k\leq M $ ). - $ 1\leq Q\leq 2\,000 $ . - $ 1\leq B_1 < B_2 < \cdots < B_Q\leq 2N $ . - All input values are integers.