Tree and Hamilton Path

给你一棵树N个顶点，N-1条带权边

还有有一张 N个点的完全图，图上两点之间的边的边权为它们在树上的距离。

求最长哈密顿路径（即不重不漏恰好经过每个点一次）。

Format
Input
第一行给出数字N

接下来N-1行描述这个树,树的边权小于等于1e9

n≤1e5

Output
One integer, the sum of x and y.

Samples
输入数据 1
5
1 2 5
3 4 7
2 3 3
2 5 2
输出数据 1
38

 依据八中友好教室2的思路，我们知道如果希望边被经过的次数最多，要选重心点。

而这个题同样的发现，只要选择重心点，其将整个树分成上下结点数相等的两部分。

如上图，2上方面有1，5这两个点，下方有3,4这两个点。

于是在走边的时候，保证相邻的两个点来自上下部，

例如

1...4...5....3....2....1

这样的回路，或者

5...4...1....3....2...5

这样的回路

则走过的总权值就是一个固定值，即为

对于(u，v)这样的一条边，设以v为根的子树有size[v]个结点，则这条边走过的次数为2*Min(size[v],n-size[v])

证明如下:不妨设size[v]小于n-size[v]

则对于以v为子树内的结点，从它外面的点走到它时(u,v)这条边要走一次，从它再走出去，又要走一次。

于是上述成立。

以上图为例

[3,4]之间的边要走过2次

[2,3]之间的边要走过4次

于是当走成一条回路的时候，结果是个固定值为2*(5+2+7)+4*3=28+12=40

现在只需要每个点走一次，也就是说整个回路的最后一条边要被减去。

则当这条边为某条与重心直接相连的边，且边权最小时，结果最优。

当然如果图有两个重心的时候，减去的边权为两个重心之间的边权。。

一句话题解就是:

当N为奇数，则当上半部N/2个点，与下半部N/2个点相匹配，每次匹配都要过重心点

当N为偶数，则当上半部(N-2)/2个点，与下半部(N-2)/2个点相匹配，每次匹配都要过重心边

 （匹配方式为：从一个重心点开始，以另一个重心点为最终的结束点）

例如下图

最终结果为总代价减去3-4之间的边长

 这个应该很好想吧，因为重心点都在靠中间的位置，如果走成

1...5...2...6...3...4....1

减去[1..4]之间的边长，那就亏大了。