hewmatt10's Tourism

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

hewmatt10 is going on vacation with the love of his life, justinzhu! hewmatt10 is touring in his favourite country, the Antartic Empire. His N cities are connected by N-1 roads in the most efficient way possible, with at most 1 road between any two cities. Since hewmatt10 loves to go on dates with justinzhu across his entire empire, he built roads such that it is possible to go from one city to any other. Every city has a bus station that can drive up to A_i cities away, at the price of P_i.

hewmatt10 is currently hiding away in Antarctica to protect himself from the coronavirus. While he is in refuge, he is planning his tour. hewmatt10 will start at any city, stop at justinzhu's hometown, numbered X, and end at another city. Specifically, at city X, hewmatt10 will get off the bus, visit justinzhu, and then get back on a second bus. It is guaranteed that city X is not a leaf node (city with 1 road). hewmatt10 also enjoys taking long walks on the beach long tours, so he will only choose tours that start and end on a leaf node. In addition, he will not choose any tours that goes through any city twice, to minimize his chances of contracting the coronavirus. hewmatt10 defines a tour to "go through" a city if on his tour, a bus starts/stops at the city, or the bus drives through a city.

Unfortunately for hewmatt10, AliceW has shattered his refuge in Antarctica and taken all his money, so hewmatt10 must borrow money from justinzhu to fund their tour. He would like to borrow as little money as possible from justinzhu so he doesn't get dumped. Please help hewmatt10 find the minimum possible cost!

Input Specification

The first line will contain N, X\ (1 \le X \le N \le 10^5), (3 \le N), the number of cities in the Antartic Empire, and justinzhu's hometown.

The next N-1 lines will contain 2 integers a, b\ (1 \le a, b \le N, a \neq b), meaning that cities a and b are connected by a road.

The next line will contain N integers A_i\ (1 \le A_i < N), meaning the i^{th} city's bus station can drive A_i cities away.

The next line will contain N integers P_i\ (1 \le P_i \le 10^6), the price of using the i^{th} city's bus station.

Output Specification

The minimum cost of hewmatt10's tour across the Antartic Empire.


Subtask 1 [40%]

(3 \le N \le 10^3)

Subtask 2 [60%]

No further constraints.

Sample Input

7 1
1 2
1 3
2 4
2 5
3 6
3 7
1 3 2 4 3 5 6
2 3 5 2 3 1 3

Sample Output


Explanation for Sample

hewmatt10 first starts at city 6, goes to city 1 with a cost of 1, then goes to city 2 with a cost of 2, then goes to city 4 with a cost of 3, adding up to a total cost of 6.


There are no comments at the moment.