AT_aalc001_v 連結性 2

There is a tree with $ N $ vertices numbered from $ 1 $ to $ N $ . Edge $ i $ connects vertices $ u_i $ and $ v_i $ . An integer interval $ [a,b] $ is **good** if the subgraph induced by vertices $ a,a+1,\ldots,b $ is connected. Process $ Q $ queries. In the $ i $ -th query, you are given integers $ L_i,R_i $ . Find the number of pairs of integers $ (a,b) $ satisfying both of the following conditions: - $ L_i \leq a \leq b \leq R_i $ - The interval $ [a,b] $ is good.

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

Print $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 The following $ 9 $ intervals are good: $ [1,1], [1,5], [2,2], [2,5], [3,3], [3,5], [4,4], [4,5], [5,5] $ ### Constraints - $ 1 \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 L_i \leq R_i \leq N $ - All numerical values in the input are integers.