DMOPC '19 Contest 7 P6 - Bob Equilibrium

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem types

Bobland consists of N intersections connected by N-1 roads. There are also K shops in the city with the i-th shop being located at intersection a_i. The location of all shops are distinct. Bob knows that customer i lives at intersection i. Customer i's favourite shop is located at intersection f_i and they have a patience value of p_i.

We define the distance between two intersections x and y to be the number of roads traversed in the unique shortest path from x to y. Bob knows that all customers behave in the following manner: suppose the closest shop to intersection i is distance d away from it. If the distance from customer i to f_i is no more than d+p_i, customer i will always prefer to travel further and visit f_i instead. Otherwise, they will visit the closest shop. If multiple shops tie for the closest one, customer i will pick any one of them.

Now Bob is thinking of starting his own shop, but he needs to choose where it will be located. Luckily, Bob is so famous that if his shop ties for shortest distance to a certain customer and that customer's favourite shop is too far away, they will always visit Bob's shop. Having extreme governmental authority, Bob can also set up shop in any intersection, including ones that already have a shop. To help him determine where to set up shop, Bob asks you to determine for each intersection x, how many customers will visit his shop if it is located at x.


Note: for this problem, you will NOT be required to pass all the samples in order to receive points. In addition, you do not need to pass previous subtasks to earn points for later subtasks.

In all subtasks,
1 \le K \le N \le 300\,000
1 \le f_i, a_i \le N
0 \le p_i \le N-1

Subtask 1 [5%]

1 \le N \le 2\,000

Subtask 2 [10%]

The degree of any node is at most 2.

Subtask 3 [10%]


Subtask 4 [75%]

No additional constraints.

Input Specification

The first line contains two space-separated integers, N and K.
The next N-1 lines contain two space-separated integers, x_i y_i, describing a road connecting intersection x_i and y_i.
The next line contains K space-separated integers, a_1, a_2, \dots, a_K, the locations of the shops.
The next N lines contain two space-separated integers, f_i p_i, the favourite shop and patience value of the i-th person respectively.

Output Specification

Output one line containing N space-separated integers, the i-th of which should be the number of customers that will visit Bob's shop if he places it at intersection i.

Sample Input 1

4 1
1 2
1 3
2 4
1 1
1 0
1 1
1 0

Sample Output 1

0 2 0 1

Explanation for Sample Output 1

If Bob sets up shop in intersection 2, he will be visited by customer 2 and 4. If he sets up shop in intersection 4, he will be visited by only customer 4. He will not be visited by any customers if he sets up shop in intersections 1 or 3.

Sample Input 2

6 3
1 2
2 3
3 4
4 5
5 6
1 2 6
6 3
6 1
6 2
1 4
2 0
1 1

Sample Output 2

1 1 1 1 1 2


There are no comments at the moment.