Maximizing Salesman Tour Profit

A salesman, Xiao T, is planning a tour of several towns in a mountainous region. The region is so sparsely connected that between any two towns there is a unique route (which may pass through other towns). In each town, Xiao T can earn a certain net profit by stopping there, although the profit might be negative. Due to the inconvenient traffic, he must stop in every town he passes. However, after the first stop in any town the local demand is saturated so additional stops do not yield extra profit. Furthermore, each town (except his hometown) imposes a strict limit on the maximum number of times a foreigner may stop there. In his hometown his net profit is 0 and there is no limit on stops.

The salesman wishes to design a cyclic tour starting and ending at his hometown (town 0) so that he may obtain the maximum total profit. A tour is defined by the set of towns at which he activates his sale (i.e. obtains their net profit) – note that even if a town is not activated, if it lies on the route connecting activated towns it will still be passed (and count toward its stop‐limit). In any town (other than town 0) that is passed N times in the tour, the stop–limit for that town must be at least N. Because opting out of a tour is allowed, the maximum profit is guaranteed to be nonnegative. The output should be the maximum profit as well as whether the optimum scheme is unique (i.e. there is only one choice of activated towns achieving this maximum profit).

Important: The detailed route is not required – two plans are considered the same if the set of activated towns is identical.

Input format:
The input begins with an integer n (n ≥ 1) representing the number of towns (towns are numbered 0 to n−1, with town 0 being the hometown).
Next follow n−1 lines, each with two integers u and v (0 ≤ u,v < n), representing an undirected road connecting towns u and v. It is guaranteed that the underlying graph is a tree (i.e. there is exactly one simple path between any two towns).
Then follow n lines. The i-th of these (starting from i = 0) contains two integers: p and r, where p is the net profit obtainable at town i (which may be negative) and r is the maximum allowed number of stops for a foreigner at that town. Note that for town 0 the profit is always 0 and the stop limit can be ignored.

Output format:
Output two items separated by a space: the maximum total profit and YES (if the optimal scheme is unique) or NO (if there are multiple optimal schemes).

Note on the problem formulation:
If a set of towns F (a subset of {1,…, n−1}) is chosen for activation, then the actual tour will visit the closure S(F) which is defined as the union of town 0 and all towns on the unique simple path from town 0 to each town in F. The feasibility condition is that for every town v in S(F) with v ≠ 0 the degree of v in the induced subtree (i.e. the number of neighbors of v also in S(F)) does not exceed its allowed limit r.
The profit from a scheme F is the sum of p[v] for all v in F with p[v] > 0 (i.e. you may choose not to activate a town that gives negative profit). The objective is to choose F so that the profit is maximized (recall that F = {} is allowed yielding profit 0). Two schemes are considered different if the activated sets differ.

inputFormat

The input is given in the following order:

 n
 u1 v1
 u2 v2
 ... (n-1 lines for edges)
 p0 r0
 p1 r1
 ... (n lines for profit and limit for each town, town 0 is the hometown)

outputFormat

Output the maximum total profit and either YES if the optimal scheme is unique, or NO if there are multiple optimal schemes. Separate the two outputs by a space.

sample

3
0 1
1 2
0 100
5 2
-1 1

5 NO