AT_abc477_g [ABC477G] Frequency Query on Tree

You are given a tree with $ N $ vertices numbered $ 1 $ to $ N $ . The $ i $ -th edge connects vertex $ u_i $ and vertex $ v_i $ . Also, integer $ x_i $ is written on vertex $ i $ . Process $ Q $ queries. In each query, you are given integers $ s,t,a,b $ ; find the number of integers $ y $ satisfying the following condition. - Let $ f $ be the number of vertices with integer $ y $ written on them among the vertices on the path connecting vertex $ s $ and vertex $ t $ . Then, $ a \leq f \leq b $ holds.

The input is given from Standard Input in the following format: > $ 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 $ Each query $ \mathrm{query}_q $ is given in the following format: > $ s $ $ t $ $ a $ $ b $

Output $ Q $ lines. The $ q $ -th line should contain the answer to the $ q $ -th query.

### Sample Explanation 1 Consider the first query. The vertices on the path connecting vertex $ 1 $ and vertex $ 5 $ are, in order, vertex $ 1 $ , vertex $ 2 $ , vertex $ 3 $ , vertex $ 4 $ , and vertex $ 5 $ . The integers written on these vertices are, in order, $ 1, 2, 3, 1, 2 $ . Thus, there are three integers $ y $ satisfying the condition: $ 1,2,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 $ - The given graph is a tree. - $ 1 \leq x_i \leq N $ - $ 1 \leq s \lt t \leq N $ - $ 1 \leq a \leq b \leq N $ - All input values are integers.