If the amount of magic in the node with the minimal magic is ~1~, it is easily shown that the solution is a path of length ~1~, that exact node.

If there are nodes of magic ~1~ in the tree (in the rest of the text, one-magic node), it can be shown that a path of minimal magic (in the rest of the text, optimal path) comes in one of the two forms:

1. a path consisting of ~k~ one-magic nodes, for some ~k~
2. a path consisting of ~2k+1~ nodes where only the central node is of magic ~2~, all the rest are one-magic nodes.

The proof reduces to breaking down the assumed minimal optimal path to two suitably selected parts. Then one of the parts must also be optimal, except in the specified cases, which contradicts the fact that it is minimal.

In solving this task, we will use the weaker claim: the optimal path consists of at most one node that is not a one-magic node. Let's call a path through node ~v~ where all other nodes are one-magic nodes ~v~-good path. It is sufficient to find the longest good path for each node, because adding one-magic nodes to the end of the path decreases its magic.

In order to do this, we will use dynamic programming in two DFS traversals over the tree. Let's root the tree and, in the first DFS traversal, for each node ~v~ dynamically calculate:

1. the longest ~v~-good path that starts in ~v~ and is contained in a subtree of ~v~,
2. the same thing for each truncated subtree of ~v~ that consists of subtrees of a prefix of its children,
3. the same thing for each truncated subtree of ~v~ that consists of subtrees of a suffix of its children.

Now, using dynamic programming for prefixes and suffixes of children, we can determine the longest ~v~-good path contained in the subtree of ~v~ that doesn't contain ~u~, for each child ~u~ of node ~v~. (We take the maximum of the prefix to the child before ~u~ and the suffix from the child after ~u~.)

The previous dynamic programming approach is used in the second DFS traversal. When we're in node ~u~, using the dynamic programming approach for its parent ~v~, we can calculate the longest ~u~-good path that contains ~v~. We must take into consideration the paths that go through ~v~ that do not contain any of its children, which is solved using an additional dynamic programming approach.

When we have the longest ~v~-good path in its subtree and the longest ~v~-good path for its parent, for a node ~v~, by traversing the children of ~v~, we can easily obtain the lengths of the two longest ~v~-good paths that start in ~v~, and whose union is the required ~v~-good path. Now, we just compare the amount of magic of the longest ~v~-good paths for all nodes ~v~ and take the smallest one.