在达芬奇时代，有一个流行的儿童游戏称为连珠线。当然，这个游戏是关于珠子和线的。线是红色或蓝色的，珠子被编号为 11 到 nn。这个游戏从一个珠子开始，每次会用如下方式添加一个新的珠子：

Append(w, v)：一个新的珠子 $w$ 和一个已经添加的珠子 v 用红线连接起来。

Insert(w, u, v)：一个新的珠子$w$插入到用红线连起来的两个珠子$u,v$之间。具体过程是删去 u, vu,v 之间红线，分别用蓝线连接 uu,w 和 w, v。

每条线都有一个长度。游戏结束后，你的最终得分为蓝线长度之和。

给你连珠线游戏结束后的游戏局面，只告诉了你珠子和链的连接方式以及每条线的长度，没有告诉你每条线分别是什么颜色。

你需要写一个程序来找出最大可能得分。即，在所有以给出的最终局面结束的连珠线游戏中找出那个得分最大的，然后输出最大可能得分。

第一行一个正整数 $n$，表示珠子的数量。珠子从 1 到 n 编号。

接下来 n - 1 行每行三个整数 $a_{i},b_{i},c_{i}$?。保证 $1 \leqslant a_{i},b_{i} \leqslant n$，$1 \leqslant c_{i} \leqslant 10000$。表示 ai? 号珠子和 bi? 号珠子间连了长度为 ci? 的线。

输出一个整数，表示最大可能得分。

5
1 2 10
1 3 40
1 4 15
1 5 20

140

【样例描述1】

可以通过如下方式获得 60 分：首先从 3 号珠子开始。

把 5 和 3 连起来。（线长度任意）

在 3 和 5 之间插入 $11$。（线长分别为 40 和 20）。

把 2 和 1 用长度为 $10$ 的线连起来。

把 4 和 1 用长度为 $15$ 的线连起来。

【限制与约定】

第一个子任务共 13 分，满足 $1\leqslant n \leqslant 10$

第二个子任务共 15 分，满足 $1\leqslant n \leqslant 200$

第三个子任务共 29 分，满足 $1\leqslant n \leqslant 10000$

第四个子任务共 43 分，满足 $1\leqslant n \leqslant 200000$

 

Solution:

为了方便，我们把每个珠子看成一个节点

我们非常开心的发现，结果肯定是一棵边颜色不同的树

由于刚开始只有任意的一个节点，就相当于我们选择一个节点为根，

然后进行两种操作：

1.每次扩展一个节点的儿子，即把一个节点和已经在树上的一个点连上一条红边，且不在这两个点之间加珠子:

或者扩展一个节点的孙子再扩展这个孙子的爸爸，就是把树上的一个节点连到另一个节点上，在把一个节点插到这两个节点之间，把两条边染成蓝色，即：

 好的，假设以1号点为根，我们可以列出一个DP方程式

f[i][0/1]表示当前节点是否为中点获得的最大价值

$f[i][0]=\sum\limits_{j}^{j \in son[i]}max(f[j][0],f[j][1]+dis(i,j));$