Daily Running

Problem Source

NOIP 2016

Problem Description

Little C thinks running is a lot of fun, so he decides to make a game called "Daily Running". "Daily Running" is a nurturing game in which players must log in on time every day to complete a check-in task.

The game map can be viewed as a tree with $n$ nodes and $n-1$ edges, where each edge connects two nodes and any two nodes are reachable from each other by a path. The nodes are numbered $1$ to $n$ (consecutive positive integers).

There are $m$ players. The $i$-th player has start point $S_i$ and end point $T_i$. When the daily check-in task begins, all players start simultaneously from their own start at second $0$, running non-stop along the shortest path toward their own end at a speed of one edge per second. A player finishes the check-in task once they reach their end. (Because the map is a tree, each player's path is unique.)

Little C wants to know the game's activity level, so he places an observer at each node. The observer at node $j$ chooses to observe players at second $W_j$. A player is observed by this observer if and only if the player also arrives at node $j$ exactly at second $W_j$. Little C wants to know how many players each observer will observe.

Note: A player ends the game upon reaching their end, and cannot wait around to be observed later. That is, for a player whose end point is node $j$: if they arrive at the end before second $W_j$, the observer at node $j$ cannot observe them; if they arrive at node $j$ exactly at second $W_j$, the observer at node $j$ can observe them.

Input Format

Read the data from standard input.

The first line contains two integers $n, m$ ($1\leq n, m\leq 3\times 10^5$). Here $n$ is the number of nodes in the tree (and also the number of observers), and $m$ is the number of players.

The next $n-1$ lines each contain two integers $u$ and $v$, indicating an edge between node $u$ and node $v$.

The next line contains $n$ integers, where the $j$-th integer is $W_j$, the time at which the observer at node $j$ appears.

The next $m$ lines each contain two integers $S_i$ and $T_i$, the start and end of a player.

For all data, $1 \leq S_i, T_i \leq n$ and $0 \leq W_j \leq n$ are guaranteed.

Output Format

Write the output to standard output.

Output a single line of $n$ integers, where the $j$-th integer is the number of players that the observer at node $j$ can observe.

Sample Input 1

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

Sample Output 1

2 0 0 1 1 1

Sample Input 2

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

Sample Output 2

1 2 1 0 1

Sample Explanation

• For node 1, $W_1=0$, so only players starting at node 1 are observed. Players 1 and 2 start at node 1, so 2 players are observed.
• For node 2, no player is at this node at second 2, so 0 players are observed.
• For node 3, no player is at this node at second 5, so 0 players are observed.
• For node 4, player 1 is observed, so 1 player is observed.
• For node 5, player 1 is observed, so 1 player is observed.
• For node 6, player 3 is observed, so 1 player is observed.