#2009. [APIO2014] 连珠线

[APIO2014] 连珠线

题目描述

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

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

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

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

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

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

输入格式

第一行一个正整数 nn,表示珠子的数量。珠子从 11nn 编号。

接下来 n1n - 1 行每行三个整数 ai,bi,cia_i, b_i, c_i。保证 1ai<bin1 \leq a_i < b_i \leq n1ci100001 \leq c_i \leq 10000。表示 aia_i 号珠子和 bib_i 号珠子间连了长度为 cic_i 的线。

输出格式

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

5
1 2 10
1 3 40
1 4 15
1 5 20
60
10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34
140

提示

【样例描述1】

可以通过如下方式获得 6060 分:首先从 33 号珠子开始。

5533 连起来。(线长度任意)

3355 之间插入 11。(线长分别为 40402020)。

2211 用长度为 1010 的线连起来。

4411 用长度为 1515 的线连起来。

【限制与约定】

第一个子任务共 13 分,满足 1n101 \leq n \leq 10

第二个子任务共 15 分,满足 1n2001 \leq n \leq 200

第三个子任务共 29 分,满足 1n100001 \leq n \leq 10000

第四个子任务共 43 分,满足 1n2000001 \leq n \leq 200000