Claws

Interview

Time limit2sMemory limit512 MB

Summary

Compute each hinge grade from subtree and root-path bar weights and report the largest root-to-claw sum of grades over all claws.

Level: Medium4 of 10
Topics: Tree, DFS
Solved: No attempts yet

Problem

Consider a piece of heavy machinery shaped like a binary tree, meaning every non-leaf node has at most two child nodes, as shown in Figure 1. The edges of the tree are metal bars, joined by hinges that sit at the nodes of the tree. The nodes are labelled 1 through 5 in the figure. The leaf nodes of the tree in Figure 1(a) are the claws that the machinery uses for heavy-duty work. The claws are attached to metal bars by hinges as well.

Figure 1: (a) a tree and (b) the corresponding tree of claws.

The machinery has to bear load, so every hinge that joins metal bars must be of the correct grade. For a node $v$ of the tree, the grade of the hinge used at that node is the sum of (i) the total weight of the metal bars in the subtree rooted at $v$ and (ii) the total weight of the metal bars on the path from $v$ to the root of the tree.

Figure 1 shows the weight of each metal bar beside the corresponding edge. The claws and the hinges are made of superlight material, so treat them as weightless. The hinges at leaf nodes 1, 2, and 3, which attach the claws to metal bars, therefore have grades 50, 30, and 50. The hinge at node 4 has grade 60, and the hinge at the root node 5 has grade 110.

The unladen load of a claw is the sum of the grades of the hinges along the path from that claw to the root node. In this example the unladen loads are 220 at node 1, 200 at node 2, and 160 at node 3. Output the maximum unladen load among all the claws of the given machinery.

Input

The input consists of $n$ lines. The first line contains the number of nodes $n$ ( $1 \le n \le 12000$ ) in the binary tree. Each of the next $n - 1$ lines contains three integers separated by spaces:

thisnode, the number of the current node.
parnode, the number of the parent of the current node.
weight, the weight of the metal bar joining the current node and its parent. It is a positive integer at most 100.

The nodes are labelled 1 through $n$ . The root is the node that has no parent.

Output

Print one integer, the maximum unladen load among all the claws of the given machinery.

Examples1

Example 1
Input
```
5
1 4 30
4 5 20
2 4 10
3 5 50
```
Expected output
```
220
```