## DMOPC '19 Contest 7 P6 - Bob Equilibrium

View as PDF

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

Author:
Problem types

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

We define the distance between two intersections and to be the number of roads traversed in the unique shortest path from to . Bob knows that all customers behave in the following manner: suppose the closest shop to intersection is distance away from it. If the distance from customer to is no more than , customer will always prefer to travel further and visit instead. Otherwise, they will visit the closest shop. If multiple shops tie for the closest one, customer 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 , how many customers will visit his shop if it is located at .

#### Constraints

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.

The degree of any node is at most .

#### Input Specification

The first line contains two space-separated integers, and .
The next lines contain two space-separated integers, , describing a road connecting intersection and .
The next line contains space-separated integers, , the locations of the shops.
The next lines contain two space-separated integers, , the favourite shop and patience value of the -th person respectively.

#### Output Specification

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

#### Sample Input 1

4 1
1 2
1 3
2 4
1
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 , he will be visited by customer and . If he sets up shop in intersection , he will be visited by only customer . He will not be visited by any customers if he sets up shop in intersections or .

#### 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