题解告诉我们，这道题答案在一棵 \(n\) 个节点的树上。
定义 \(f(l,r)\) 表示让编号在区间 \([l,r]\) 内所有点连通需要的最少边数，答案就是

题解给了代码，但你一看就知道时间复杂度不对，那份代码必然TLE。
于是你放弃了借鉴题解的打算，下定决心自己写一份标程。

第一行一个整数 \(n\) ，接下来 \(n-1\) 行每行两个整数 \(x,y\) 表示一条边。

一个整数答案。

样例1

样例输入

4
1 4
1 3
2 4

样例输出

16

数据范围

对于全部测试数据， $1\leq n\leq 10^5$ ， $1\leq x,y\leq n$ 。

20% n<=10
40% n<=300
60% n<=3000
另外20% 一条链
100% n<=100000