3647 [APIO2014] Lianzhu line< /h1>
Title description< /h2>
During the Da Vinci era, there was a popular children’s game called Renzhu Line. Of course, this game is about beads and threads. The thread is red or blue, and the beads are numbered 1< span class="strut bottom">1 to nn. This game starts with a bead, and each time a new bead is added in the following way:
Append(w, v): a new bead $w$< span class="mord mathit"> and an added bead v Connect with a red line. span>
Insert(w, u, v): a new bead $w$insert into the two connected by a red line Beads $u,v$. The specific process is to delete u, vu,v 之Connect the red lines between uu,w And w, v< span class="base">. span> span>
Every line has A length. After the game is over, your final score is the sum of the length of the blue line.
Give you the game situation after the bead line game is over. It only tells you the connection method of the beads and the chain and the length of each line, but does not tell you what color each line is.
You need to write a program to find the maximum possible score. That is, among all the renju games that ended with the given final position, the one with the highest score is found, and then the largest possible score is output.
input format
A positive integer in the first line $n$ indicates the number of beads. Beads from 1 to n number. span>
Next n-1< span class="mord mathit"> Three integers per line $a_ {i},b_{i},c_{i}$ < span class="mord">< span class="mord rule">?. Guarantee $1 \leqslant a_{i},b_{i} \leqslant n$, $1 \leqslant c_{i} \leqslant 10000$< span class="mrel">< span class="mrel"> < span class="vlist-s">. Represents ai? No. beads and bi? Number of beads inter-connected The length is ci? the line. span> span> span> span> span> span>< /span>< /span>
Output format
Output an integer that represents the maximum possible score.
Input and output sample
Enter #1
5
1 2 10
1 3 40
1 4 15
1 5 20
Output#1
60
Input#2
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
output #2
140
Instructions/Tips
[Sample Description 1]
It can be obtained as follows 60 points: First start with bead number 3 starts. span>
Put 5 and < span class="katex-html">3 connected together. (Line length is arbitrary)< /span>
In 3 and 5 insert $11$< span class="katex">. (The line lengths are respectively 40and20). span> p>
put 2 and 1 The use length is $10$ to connect the lines. span>
put < span class="mord">4 and 1 The use length is $15$ to connect the lines. span>
[Restrictions and Conventions]
The first subtask has 13 points, which satisfies $1\leqslant n \leqslant 10$< /span>
The second subtask has 15 points, satisfying $1\leqslant n \leqslant 200 $
The third subtask has 29 points, satisfying $1\leqslant n \leqslant 10000$
The fourth subtask has 43 points, satisfying $1\leqslant n \leqslant 200000$< /p>
Solution:
For convenience, we treat each bead as a node
We are very happy to find that the result must be a tree with different sides
Since there is only one node at the beginning,is equivalent to choosing a node as the root,
Then do two operations:
1. Each time the son of a node is expanded, a node and a point already on the tree are connected to a red edge, and Do not add beads between these two points:
Or expand the grandson of a node and then expand the dad of this grandson Dad, just connect a node on the tree to another node, insert a node between these two nodes, and dye the two edges blue, that is: p>
Okay, assuming point 1 is the root, we can list one DP equation
f[i][0/1] indicates whether the current node is the maximum value obtained by the midpoint
$f[i][0]=\sum\limits_{j}^{j \in son[i]}max(f[ j][0],f[j][1]+dis(i,j));$
During the Da Vinci era, there was a popular children’s game called Renzhu Line. Of course, this game is about beads and threads. The thread is red or blue, and the beads are numbered 1< span class="strut bottom">1 to nn. This game starts with a bead, and each time a new bead is added in the following way:
Append(w, v): a new bead $w$< span class="mord mathit"> and an added bead v Connect with a red line. span>
Insert(w, u, v): a new bead $w$insert into the two connected by a red line Beads $u,v$. The specific process is to delete u, vu,v 之Connect the red lines between uu,w And w, v< span class="base">. span> span>
Every line has A length. After the game is over, your final score is the sum of the length of the blue line.
Give you the game situation after the bead line game is over. It only tells you the connection method of the beads and the chain and the length of each line, but does not tell you what color each line is.
You need to write a program to find the maximum possible score. That is, among all the renju games that ended with the given final position, the one with the highest score is found, and then the largest possible score is output.
A positive integer in the first line $n$ indicates the number of beads. Beads from 1 to n number. span>
Next n-1< span class="mord mathit"> Three integers per line $a_ {i},b_{i},c_{i}$ < span class="mord">< span class="mord rule">?. Guarantee $1 \leqslant a_{i},b_{i} \leqslant n$, $1 \leqslant c_{i} \leqslant 10000$< span class="mrel">< span class="mrel"> < span class="vlist-s">. Represents ai? No. beads and bi? Number of beads inter-connected The length is ci? the line. span> span> span> span> span> span>< /span>< /span>
Output an integer that represents the maximum possible score.
5 1 2 10 1 3 40 1 4 15 1 5 20
140
[Sample Description 1]
It can be obtained as follows 60 points: First start with bead number 3 starts. span>
Put 5 and < span class="katex-html">3 connected together. (Line length is arbitrary)< /span>
In 3 and 5 insert $11$< span class="katex">. (The line lengths are respectively 40and20). span> p>
put 2 and 1 The use length is $10$ to connect the lines. span>
put < span class="mord">4 and 1 The use length is $15$ to connect the lines. span>
[Restrictions and Conventions]
The first subtask has 13 points, which satisfies $1\leqslant n \leqslant 10$< /span>
The second subtask has 15 points, satisfying $1\leqslant n \leqslant 200 $
The third subtask has 29 points, satisfying $1\leqslant n \leqslant 10000$
The fourth subtask has 43 points, satisfying $1\leqslant n \leqslant 200000$< /p>
Solution:
For convenience, we treat each bead as a node
We are very happy to find that the result must be a tree with different sides
Since there is only one node at the beginning,is equivalent to choosing a node as the root,
Then do two operations:
1. Each time the son of a node is expanded, a node and a point already on the tree are connected to a red edge, and Do not add beads between these two points:
Or expand the grandson of a node and then expand the dad of this grandson Dad, just connect a node on the tree to another node, insert a node between these two nodes, and dye the two edges blue, that is: p>
Okay, assuming point 1 is the root, we can list one DP equation
f[i][0/1] indicates whether the current node is the maximum value obtained by the midpoint
$f[i][0]=\sum\limits_{j}^{j \in son[i]}max(f[ j][0],f[j][1]+dis(i,j));$
3647 [APIO2014] Lianzhu thread
3647 [APIO2014] Lianzhu thread
Title description
During the time of Da Vinci, there was a popular children’s game called renju line. Of course, this game is about beads and threads. The thread is red or blue, and the beads are numbered 1< span class="strut bottom">1 to nn. This game starts with a bead, and each time a new bead is added in the following way:
Append(w, v): a new bead $w$< span class="mord mathit"> and an added bead v Connect with a red line. span>
Insert(w, u, v): a new bead $w$insert into the two connected by a red line Beads $u,v$. The specific process is to delete u, vu,v 之Connect the red lines between uu,w And w, v< span class="base">. span> span>
Every line has A length. After the game is over, your final score is the sum of the length of the blue line.
Give you the game situation after the bead line game is over. It only tells you the connection method of the beads and the chain and the length of each line, but does not tell you what color each line is.
You need to write a program to find the maximum possible score. That is, among all the renju games that ended with the given final position, the one with the highest score is found, and then the largest possible score is output.
input format
A positive integer in the first line $n$ indicates the number of beads. Beads from 1 to n number. span>
Next n-1< span class="mord mathit"> Three integers per line $a_ {i},b_{i},c_{i}$ < span class="mord"> ?. Guarantee $1 \leqslant a_{i},b_{i} \leqslant n$, $1 \leqslant c_{i} \leqslant 10000$< span class="mrel">< span class="mrel"> < span class="vlist-s">. Represents ai? No. beads and bi? Number of beads inter-connected The length is ci? the line. span> span> span> span>
输出格式
输出一个整数，表示最大可能得分。
输入输出样例
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));$
