AT_joi2026final_e JOI ツアー 2 (JOI Tour 2)

JOI 国には $ N $ 個の街があり， $ 1 $ から $ N $ までの番号が付けられている．また，JOI 国には $ N-1 $ 本の道路があり， $ 1 $ から $ N-1 $ までの番号が付けられている． 道路 $ j $ ( $ 1\leqq j\leqq N-1 $ ) は街 $ U_j $ と街 $ V_j $ を双方向に結んでいる．どの街からどの街へも何本かの道路を通ることによって移動することができる． JOI 国のそれぞれの街には店が $ 1 $ つあり，街 $ i $ ( $ 1\leqq i\leqq N $ ) の店ではお土産を値段 $ A_i $ で売っている． JOI 国では今年， $ M $ 個のツアーが計画されている． $ k $ 番目 ( $ 1\leqq k\leqq M $ ) のツアーは，街 $ S_k $ を出発し，街 $ T_k $ まで同じ街を $ 2 $ 回訪れることなく道路を通って移動するものである．ただし $ k $ 番目のツアーは街 $ S_k, T_k $ も訪れる．また， $ S_k\neq T_k $ であることが保証される． JOI 国の構造から，ツアーがどの街を訪れるかが $ 1 $ 通りに定まることに注意せよ． あなたは，これらのツアーのうちひとつに参加して，訪れる街のうちちょうど $ 2 $ つの街でお土産を $ 1 $ つずつ購入することを計画している． さらに，お土産のために用意した予算をちょうど使い切るようにしたいと考えているため， $ Q $ 通りの予算の候補についてそのような方法が何通りあるのかを調べることにした． JOI 国の道路とお土産の値段，ツアーの情報，および予算の候補 $ B_1, B_2, \ldots, B_Q $ が与えられたとき， ツアーおよびお土産を購入する街を選ぶ方法が何通りあるかを求めるプログラムを作成せよ． より形式的には各 $ q $ ( $ 1\leqq q\leqq Q $ ) について，整数の組 $ (k,u,v) $ であって以下の条件をすべて満たすものの個数を求めるプログラムを作成せよ． - $ 1\leqq k\leqq M $ ． - $ 1\leqq u < v \leqq N $ ． - $ k $ 番目のツアーは街 $ u, v $ を訪れる． - $ A_u+A_v=B_q $ ． ---

入力は以下の形式で標準入力から与えられる． > $ 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 $

標準出力に $ Q $ 行出力せよ． $ q $ 行目 ( $ 1\leqq q\leqq Q $ ) には，予算 $ B_q $ をちょうど使い切るようにツアーおよびお土産を購入する街を選ぶ方法が何通りあるかを出力せよ． ---

### 小課題 1. ( $ 3 $ 点) $ N\leqq 100 $ ， $ M\leqq 100 $ ， $ Q\leqq 100 $ ． 2. ( $ 4 $ 点) $ N\leqq 5\,000 $ ， $ U_j=j $ ( $ 1\leqq j\leqq N-1 $ )， $ V_j=j+1 $ ( $ 1\leqq j\leqq N-1 $ )． 3. ( $ 5 $ 点) $ N\leqq 5\,000 $ ． 4. ( $ 6 $ 点) $ Q= 1 $ ， $ U_j=j $ ( $ 1\leqq j\leqq N-1 $ )， $ V_j=j+1 $ ( $ 1\leqq j\leqq N-1 $ )． 5. ( $ 10 $ 点) $ Q= 1 $ ． 6. ( $ 7 $ 点) $ M\leqq 1000 $ ， $ U_j=j $ ( $ 1\leqq j\leqq N-1 $ )， $ V_j=j+1 $ ( $ 1\leqq j\leqq N-1 $ )． 7. ( $ 12 $ 点) $ M\leqq 1000 $ ． 8. ( $ 10 $ 点) $ N\leqq 50\,000 $ , $ M\leqq 50\,000 $ ， $ U_j=j $ ( $ 1\leqq j\leqq N-1 $ )， $ V_j=j+1 $ ( $ 1\leqq j\leqq N-1 $ )． 9. ( $ 15 $ 点) $ N\leqq 50\,000 $ , $ M\leqq 50\,000 $ ． 10. ( $ 11 $ 点) $ U_j=j $ ( $ 1\leqq j\leqq N-1 $ )， $ V_j=j+1 $ ( $ 1\leqq j\leqq N-1 $ )． 11. ( $ 17 $ 点) 追加の制約はない． --- ### Sample Explanation 1 まずそれぞれのツアーが訪れる街は次の通りである． - $ 1 $ 番目のツアーは街 $ 1, 2, 3, 4 $ を訪れる． - $ 2 $ 番目のツアーは街 $ 1, 6 $ を訪れる． - $ 3 $ 番目のツアーは街 $ 2, 5 $ を訪れる． - $ 4 $ 番目のツアーは街 $ 3, 7, 8 $ を訪れる． $ k $ 番目のツアーに参加して街 $ u, v $ でお土産を購入するという方法を $ (k,u,v) $ と表すとき，それぞれの予算の候補について，予算を使い切る方法は次の通りである． - 予算 $ 1 $ を使い切る方法は $ 0 $ 通りである． - 予算 $ 2 $ を使い切る方法は $ 0 $ 通りである． - 予算 $ 3 $ を使い切る方法は $ (1,1,2) $ , $ (1,1,4), (2,1,6), (3,2,5) $ の $ 4 $ 通りである． - 予算 $ 4 $ を使い切る方法は $ (1,1,3) $ , $ (1,2,4) $ の $ 2 $ 通りである． - 予算 $ 5 $ を使い切る方法は $ (1,2,3),(1,3,4),(4,3,8),(4,7,8) $ の $ 4 $ 通りである． - 予算 $ 6 $ を使い切る方法は $ (4,3,7) $ の $ 1 $ 通りである． - 予算 $ 16 $ を使い切る方法は $ 0 $ 通りである． この入力例は小課題 $ 1, 3, 7, 9, 11 $ の制約を満たす． --- ### Sample Explanation 2 この入力例は小課題 $ 1, 2, 3, 6, 7, 8, 9, 10, 11 $ の制約を満たす． ### Constraints - $ 2 \leqq N \leqq 100\,000 $ ． - $ 1\leqq A_i\leqq N $ ( $ 1 \leqq i \leqq N $ )． - $ 1\leqq U_j\leqq N $ ( $ 1 \leqq j \leqq N-1 $ )． - $ 1\leqq V_j\leqq N $ ( $ 1 \leqq j \leqq N-1 $ )． - どの $ 2 $ つの街の間も，いくつかの道路を経由して移動することができる． - $ 1\leqq M \leqq 200\,000 $ ． - $ 1\leqq S_k\leqq N $ ( $ 1\leqq k\leqq M $ )． - $ 1\leqq T_k\leqq N $ ( $ 1\leqq k\leqq M $ )． - $ S_k\neq T_k $ ( $ 1\leqq k\leqq M $ )． - $ 1\leqq Q\leqq 2\,000 $ ． - $ 1\leqq B_1 < B_2 < \cdots < B_Q\leqq 2N $ ． - 入力される値はすべて整数である．