AT_past202212_m 木と区間

$ N $ 頂点の木があり、頂点は $ 1, \dots, N $ と、辺は $ 1, \dots, N-1 $ と番号付けられています。辺 $ i \, (1 \leq i \leq N - 1) $ は頂点 $ U_i, V_i $ を結んでいます。 $ 1 \leq l \leq r \leq N - 1 $ を満たす全ての整数組 $ (l, r) $ に対する以下の値の総和を求めてください。 - 頂点 $ 1 $ から出発し、番号が $ l $ 以上 $ r $ 以下である辺のみを $ 0 $ 本以上辿って到達することができる頂点の個数。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ U_1 $ $ V_1 $ $ \vdots $ $ U_{N - 1} $ $ V_{N - 1} $

答えを出力せよ。

### Sample Explanation 1 たとえば、 $ (l, r) = (2, 4) $ のとき、頂点 $ 1 $ から到達することができるのは頂点 $ 1, 2, 4 $ であり、 $ (l, r) = (3, 3) $ のとき、頂点 $ 1 $ から到達することができるのは頂点 $ 1 $ のみです。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq N - 1) $ - 与えられるグラフは木 - 入力は全て整数