Dadas manages a project that depends on many packages. The dependency structure is given as a tree rooted at vertex . Vertex represents the project itself, and every other vertex represents a package.
Some packages may have security vulnerabilities. You may perform the following two operations.
--force patch: Force-update package . This costs and fixes every vulnerability at and all descendants of . This operation may be performed even if itself is not vulnerable.The affected vertices of every operation are determined by the original tree. Operations do not change the tree structure or any cost, create new vulnerabilities, or restore vulnerabilities that have already been fixed.
At most --force patches may be performed. There is no limit on the number of normal patches. No operation may be performed on vertex .
Find the minimum total cost required to fix all vulnerabilities.
The input is given from Standard Input in the following format:
For each test case, print the minimum total cost required to fix all vulnerabilities on one line.
In the first test case, applying --force to package fixes the vulnerabilities at packages and for cost . Applying --force to package costs another , for a total cost of .
Each case is given in the following format:
The -th edge connects vertices and . Parent-child relations are defined after rooting the tree at vertex .
means that package is vulnerable, and means that it is not vulnerable.
is the cost of applying a normal patch to package . If package is not vulnerable, then .
is the cost of applying a --force patch to package .
| 4 | 50 | No additional constraints. |