4101. 连珠线

【题目背景】

HS玩原审玩沙了，为了拿到更多原石去给尤拉爆金币，他不得不游玩原审的小游戏连珠线

【题目描述】

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

1.一个新的珠子 w 和一个已经添加的珠子 v 用红线连接起来。

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

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

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

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

【输入格式】

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

接下来n-1一行每行3个整数xyz表示x到y连了一条长度为z的边

【输出格式】

输出蓝线最大长度

【样例输入】

5



1 2 10



1 3 40



1 4 15



1 5 20

【样例输出】

60

【样例说明】

【数据规模与约定】

数据按组给分

part1:10pts 与样例一致

part1:10pts n<=10

part2:20pts n<=200

part3:60pts n<=1e5

对于100%的数据 z<=1e4

【来源】

[APIO2014] 连珠线

https://www.luogu.com.cn/problem/P3647