P6082 [JSOI2015] salesman

A salesman, Little T, needs to travel to several towns to sell goods. Since this area is a mountainous region with inconvenient transportation, between any two towns there is exactly one possible route (which may pass through other towns). Little T can accurately estimate the net profit of staying in each town. These net profits may be negative, meaning the sales profit does not cover the cost. Because transportation is inconvenient, every time Little T passes through a town, he must stop there. The number of stops in a town is unrelated to the net profit there, because many costs are not charged per visit, and each town’s demand for Little T’s goods is relatively fixed and becomes saturated after one visit. To strengthen public security, each town has a strict limit on the maximum number of times an outsider may stay there. Please help Little T design a tour plan with the maximum total profit: start from his hometown, stop in every town he passes through, and finally return to his hometown. Your program only needs to output the maximum profit, and whether the optimal plan is unique. A plan does not include route details; two plans are considered the same if and only if the set of towns that are visited and stayed in is the same. Since canceling the tour is also a valid plan, the maximum profit will not be negative. Little T’s net profit in his hometown is $0$, because he is a local there, and of course there is no limit on the number of stays in his hometown.

The first line contains a positive integer $n$, the number of towns. The towns are numbered from $1$ to $n$. Little T’s hometown is town $1$. The second and third lines each contain $n-1$ integers separated by spaces. The $i$-th number on the second line represents the net profit of staying in town $i+1$. The $i$-th number on the third line represents the maximum allowed number of stays in town $i+1$. All maximum stay counts are at least $2$. The next $n-1$ lines each contain two positive integers $x, y$ between $1$ and $n$, separated by a space, indicating that there is a bidirectional road directly connecting $x$ and $y$ without passing through other towns. The input guarantees that all towns are connected.

Output two lines. The first line contains a non-negative integer, the maximum profit of the tour. If the optimal plan is unique, output `solution is unique` on the second line; otherwise output `solution is not unique`.

#### Sample Explanation The best route includes towns $1, 2, 4, 5, 9$. --- #### Constraints For $100\%$ of the testdata, $5 \leq n \leq 10^5$. Translated by ChatGPT 5