Alice and Bob are playing games again! This time, they invent a new game called "Color the Tree". They draw a tree with N nodes and, certainly, (N-1) edges connecting them to assure a path between each pair of the nodes. But the tree they play with is a little special - each edge is assigned to a color and a specific value. Initially, the value of each edge is settled while the colors are all white.
When the game starts, Alice and Bob each choose a node as her/his starting node. In each round, Alice firstly makes a move from her current node to another through an edge with a color of white or red, and if the edge is white, she colors it to red. After that, Bob makes a similar move through a white or blue edge from his current node, and if the edge is white, he colors it to blue. The game keeps going on until all the edges are colored to either red or blue.
Alice's goal is to maximize the sum of values of the red edges, and Bob, wants to maximize that of the blue edges. Given the starting node of them, figure out the maximum sum that Alice is able to obtain if both of them take the best strategy in each round.