[ABC298Ex] Sum of Min of Length

给定一棵有 $n$ 个结点的树，共 $m$ 次询问，每次询问结点 $L,R$，求 $\begin{aligned}\sum_{i=1}^n\min\{d(i,L),d(i,R)\}\end{aligned}$，其中 $d(x,y)$ 表示 $x$ 结点到 $y$ 结点的距离。 translated by 月。

[problemUrl]: https://atcoder.jp/contests/abc298/tasks/abc298_h $ N $ 頂点の木が与えられます。頂点には $ 1 $ から $ N $ までの番号がついており、$ i $ 番目の辺は頂点 $ A_i $ と頂点 $ B_i $ を結んでいます。 また、この木における頂点 $ x $ と頂点 $ y $ の距離を $ d(x,y) $ で表します。ただし、頂点 $ x $ と頂点 $ y $ の距離とは、頂点 $ x $ から頂点 $ y $ までの最短パス上の辺の本数のことをいいます。 $ Q $ 個のクエリが与えられるので、順番に答えてください。$ i $ 番目のクエリは以下で説明されます。 - 整数 $ L_i,\ R_i $ が与えられます。 $ \displaystyle\sum_{j\ =\ 1}^{N}\ \min(d(j,\ L_i),\ d(j,\ R_i)) $ の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ B_1 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ Q $ $ L_1 $ $ R_1 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。

5
3 4
4 5
2 5
1 5
3
4 1
1 2
5 3

4
6
3

8
4 2
4 1
5 6
6 1
7 6
8 1
3 7
7
8 4
4 4
7 2
4 4
5 3
4 4
6 1

14
16
10
16
14
16
8

### 制約 - $ 1\ \leq\ N,\ Q\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ A_i,\ B_i,\ L_i,\ R_i\ \leq\ N $ - 与えられるグラフは木 - 入力はすべて整数 ### Sample Explanation 1 $ 1 $ 番目のクエリについて説明します。 $ d(1,\ 4)\ =\ 2 $、$ d(1,\ 1)\ =\ 0 $ より $ \min(d(1,\ 4),\ d(1,\ 1))\ =\ 0 $ です。 $ d(2,\ 4)\ =\ 2 $、$ d(2,\ 1)\ =\ 2 $ より $ \min(d(2,\ 4),\ d(2,\ 1))\ =\ 2 $ です。 $ d(3,\ 4)\ =\ 1 $、$ d(3,\ 1)\ =\ 3 $ より $ \min(d(3,\ 4),\ d(3,\ 1))\ =\ 1 $ です。 $ d(4,\ 4)\ =\ 0 $、$ d(4,\ 1)\ =\ 2 $ より $ \min(d(4,\ 4),\ d(4,\ 1))\ =\ 0 $ です。 $ d(5,\ 4)\ =\ 1 $、$ d(5,\ 1)\ =\ 1 $ より $ \min(d(5,\ 4),\ d(5,\ 1))\ =\ 1 $ です。 $ 0\ +\ 2\ +\ 1\ +\ 0\ +\ 1\ =\ 4 $ であるため、$ 4 $ を出力します。