E-小红的陡峭值（四）_牛客周赛 Round 84

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小红定义一棵树的陡峭值为：每一条边连接的两个相邻节点，编号差值的绝对值之和；若一棵树只有 $1$ 个节点，则该树的陡峭值为 $0$ 。例如，对于一棵由 $3$ 个节点组成的树，若节点 $2$ 和节点 $3$ 连边，节点 $3$ 和节点 $1$ 连边，则该树的陡峭值为 $|2-3|+|3-1|=3$ 。
$\hspace{15pt}$ 现在小红拿到了一棵由 $n$ 个节点组成的树，她准备断掉一条树边，使得形成两棵树。小红希望这两棵树的陡峭值尽可能的接近。请你求出这两棵树陡峭值之差的绝对值的最小值。

输入描述:

第一行输入一个正整数  代表树上的节点数量。 
此后的  行，第  行输入两个正整数  代表第  条边连接的节点  和 。保证这棵树是一棵合法的树。

输出描述:

输出一个整数，代表绝对值的最小值。

示例1

输入

复制

3
2 3
3 1

输出

复制

说明

断掉第二条边后，两棵树的陡峭值分别为  和 ，可以证明差值的绝对值最小为 。