[ARC183D] Keep Perfectly Matched

给一棵 $n$ 个点的无根树（$n$ 为偶数），$n-1$ 条边，其中每条边 $A_i,B_i$ 表示将这两个点连起来。

特别地，对于前 $\frac n2$ 条边，$A_i=2\times i-1,B_i=2\times i$，容易发现这张图存在完美匹配。

接下来你需要操作 $\frac n2$ 次，对于每次操作选择两个叶子 $u,v$，删掉这两个点，可以获得一个权值 $V$，$V$ 的权值为 $u,v$ 两点最短路含有的边的数量，同时你需要保证每次操作完之后，这棵树仍然有完美匹配。

问操作 $\frac n2$ 次之后，权值和最大是多少（不要求输出），构造方案。

• $2\le N\le 250000$。
• $N$ 是偶数。
• $1\le A_i<B_i\le N(1\le i\le N-1)$。
• $A_i=2\times i-1,B-i=2\times i(1\le i\le N/2)$。
• 保证所有输入均为整数，且图为一棵树。

translated by daduoli.