AT_abc438_f [ABC438F] Sum of Mex

$ N $ 頂点の木 $ T $ が与えられます。各頂点には $ 0 $ から $ N-1 $ までの番号がついており、 $ i $ 番目 $ (1\le i\le N-1) $ の辺は頂点 $ u_i $ と頂点 $ v_i $ を双方向に繋いでいます。（頂点番号は 0-indexed で辺番号が 1-indexed であることに注意してください。） $ 0 $ 以上 $ N $ 未満の整数の組 $ (i,j) $ に対し $ f(i,j) $ を以下のように定めます： - 木 $ T $ の頂点 $ i $ から頂点 $ j $ までのパスに **含まれない** 頂点のうち番号が最も小さい頂点の頂点番号。 - ただし、頂点 $ i $ から頂点 $ j $ までのパスに頂点 $ 0 $ から頂点 $ N-1 $ まで全ての頂点が含まれる場合 $ f(i,j)=N $ とする。 木 $ T $ の頂点 $ i $ から頂点 $ j $ までのパスに頂点 $ i,j $ も含まれることに注意してください。 $ \displaystyle \sum_{0\le i \le j < N} f(i,j) $ の値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_{N-1} $ $ v_{N-1} $

$ \displaystyle \sum_{0\le i \le j < N} f(i,j) $ の値を出力せよ。

### Sample Explanation 1 $ f(0,0)=1,f(0,1)=2,f(1,1)=0 $ です。したがって、 $ 1+2+0=3 $ を出力してください。 ### Constraints - $ 2\le N\le 2\times 10^5 $ - $ 0\le u_i < v_i < N $ - 入力で与えられるグラフは木 - 入力される値は全て整数