AT_abc477_g [ABC477G] Frequency Query on Tree

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木が与えられます。 $ i $ 番目の辺は頂点 $ u_i $ と頂点 $ v_i $ を結んでいます。また、頂点 $ i $ には整数 $ x_i $ が書かれています。 $ Q $ 個のクエリを処理してください。クエリでは整数 $ s,t,a,b $ が与えられるので、以下の条件を満たす整数 $ y $ の個数を求めてください。 - 頂点 $ s $ と頂点 $ t $ を結ぶパス上にある頂点のうち、整数 $ y $ が書かれた頂点の個数を $ f $ とする。この時、 $ a \leq f \leq b $ が成り立つ。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ x_1 $ $ x_2 $ $ \dots $ $ x_N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリ $ \mathrm{query}_q $ は以下の形式で与えられる。 > $ s $ $ t $ $ a $ $ b $

$ Q $ 行出力せよ。 $ q $ 行目には $ q $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目のクエリを考えます。 頂点 $ 1 $ と頂点 $ 5 $ を結ぶパス上の頂点は順に頂点 $ 1 $ 、頂点 $ 2 $ 、頂点 $ 3 $ 、頂点 $ 4 $ 、頂点 $ 5 $ です。 各頂点に書かれている整数は順に $ 1, 2, 3, 1, 2 $ です。よって、条件を満たす整数 $ y $ は $ 1,2,3 $ の $ 3 $ 個です。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq u_i \lt v_i \leq N $ - 入力で与えられるグラフは木 - $ 1 \leq x_i \leq N $ - $ 1 \leq s \lt t \leq N $ - $ 1 \leq a \leq b \leq N $ - 入力される値は全て整数