# KOITST 24 Virus

https://www.acmicpc.net/problem/31573

KOI City suffered significant damage due to the recent COVID-19 pandemic, so it is determined to thoroughly prepare for any potential pandemic situations that may arise in the future. To achieve this, KOI City wants to analyze how vulnerable its current city structure is to viruses.

KOI City consists of $N$ locations and $N - 1$ bidirectional roads, allowing travel between any two distinct locations using only roads. In other words, the city's road network forms a tree structure. Each location is identified by a unique integer ranging from $0$ to $N - 1$. Since the road network in KOI City is a tree, there is a unique simple path between any two locations $u$ and $v$. Let's define the distance between $u$ and $v$ as the number of edges in the unique path between them.

In KOI City, there are $M$ people living. For all $0 ≤ j ≤ M - 1$, the $j$-th person lives at location $P[j]$ and can travel to locations within a distance of $D[j]$ from their residence.

Virologists in KOI City have modeled the process of virus transmission between two individuals as follows: For all $0 ≤ v ≤ N - 1$, the time of propagation at location $v$ is represented by the positive integer $C[v]$. Suppose the $j$-th person was initially infected with the virus at time $t$, and let $k$ denote the person who will receive the virus from person $j$. If location $w$ is reachable by both person $j$ and person $k$ - in other words, if the distance between location $w$ and location $P[j]$ is at most $D[j]$ and the distance between location $w$ and location $P[k]$ is at most $D[k]$ - then location $w$ becomes a medium of transmission.

If there is no medium of transmission, person $k$ will not be directly infected by person $j$. However, indirect infection through other individuals is still possible. If there is a medium of transmission, and among those media, the number of locations where transmission occurs at the earliest time is denoted by $x$, if person $k$ is not infected by the virus at time $t + C[x]$, then person $k$ will be infected by person $j$ at that time. The virus spreads according to this formula for all distinct pairs of individuals $0 ≤ j, k ≤ M - 1$, where $j \ne k$.

Under this modeling, researchers in KOI City want to calculate if the $0$-th person is infected at time $0$, when does each individual $0 ≤ j ≤ M -1$ becomes infected with the virus? If person $j$ is not infected with the virus, you should record the time as $-1$.

# Function List and Definition

You must implement the following function:

`vector<long long> find_spread(int N, int M, vector<int> A, vector<int> B, vector<int> P, vector<int> D, vector<int> C)`

Parameters:

* $N$: Number of locations in KOI City.
* $M$: Number of people in KOI City.
* $A$, $B$: Arrays of length $N - 1$. For all $i$ ($0 ≤ i ≤ N - 2$), there is a road connecting location $A[i]$ and location $B[i]$. Each road appears exactly once in both arrays.
* $P$, $D$: Arrays of length $M$. For all $j$ ($0 ≤ j ≤ M - 1$), the $j$-th person lives at location $P[j]$ and can travel to locations within a distance of $D[j]$ from their residence.
* $C$: Array of length $N$. For all $v$ ($0 ≤ v ≤ N - 1$), the propagation time at location $v$ is $C[v]$.
* Return:

The function should return an array $T$ of size $M$. For all $j$ ($0 ≤ j ≤ M - 1$), $T[j]$ should be the time when the $j$-th person becomes infected with the virus for the first time if infected, and $-1$ if not infected.
The function is called exactly once for each test case.

No part of the submitted source code should execute input/output functions.

# Constraints:

* $1 ≤ N ≤ 100,000$
* $1 ≤ M ≤ 100,000$
* For all $0 ≤ i ≤ N - 2$, $0 ≤ A[i], B[i] ≤ N - 1$, $A[i] \ne B[i]$.
* For all $0 ≤ j ≤ M - 1$, $0 ≤ P[j], D[j] ≤ N - 1$.
* For all $0 ≤ v ≤ N - 1$, $1 ≤ C[v] ≤ 10^9$.

# Subtasks

### Subtask 1 (5 points)

$N ≤ 500$, $M ≤ 500$
For all $0 ≤ i ≤ N - 2$, $A[i] = i$, $B[i] = i + 1$.

### Subtask 2 (8 points)

$N ≤ 5,000$, $M ≤ 5,000$
For all $0 ≤ i ≤ N - 2$, $A[i] = i$, $B[i] = i + 1$.

### Subtask 3 (27 points)

For all $0 ≤ i ≤ N - 2$, $A[i] = i$, $B[i] = i + 1$.

### Subtask 4 (5 points)

$N ≤ 500$, $M ≤ 500$

### Subtask 5 (8 points)

$N ≤ 5,000$, $M ≤ 5,000$

### Subtask 6 (47 points)

No additional constraints.

# Examples

Example 1

Let's consider the case where $N = 8$, $M = 5$, $A = [0, 1, 2, 3, 4, 5, 6]$, $B = [1, 2, 3, 4, 5, 6, 7]$, $P = [2, 5, 7, 1, 4]$, $D = [2, 0, 0, 1, 1]$, and $C = [40, 5, 5, 16, 32, 8, 1, 10]$.

The grader calls the function as follows:

`find_spread(8, 5, [0, 1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6, 7], [2, 5, 7, 1, 4], [2, 0, 0, 1, 1], [40, 5, 5, 16, 32, 8, 1, 10])`

In this case, the virus spreads as follows:

* At time $0$, person $0$ is infected.
* At time $5$, person $3$ is infected. Person $3$ is infected by person $0$, and the medium of transmission is location $1$. (Location $2$ can also be a medium of transmission.)
* At time $16$, person $4$ is infected. Person $4$ is infected by person $0$, and the medium of transmission is location $3$.
* At time $24$, person $1$ is infected. Person $1$ is infected by person $4$, and the medium of transmission is location $5$.

Person $2$ remains uninfected throughout.

The function should return $[0, 24, -1, 5, 16]$.

Example 2

The grader calls the function as follows:

`find_spread(8, 5, [0, 1, 2, 3, 4, 3, 3], [1, 2, 3, 4, 5, 6, 7], [2, 5, 7, 1, 4], [2, 0, 0, 1, 1], [40, 5, 5, 16, 32, 8, 1, 10])`

The function should return $[0, 24, 10, 5, 16]$.

Example 3

The grader calls the function as follows:

`find_spread(10, 10, [9, 0, 1, 5, 3, 8, 0, 6, 0], [3, 6, 8, 1, 2, 7, 4, 5, 9], [9, 7, 1, 8, 6, 1, 4, 7, 5, 5], [0, 2, 0, 1, 3, 2, 6, 2, 1, 4], [10, 12, 5, 9, 8, 21, 20, 6, 13, 5])`

The function should return $[0, 11, 17, 11, 5, 11, 5, 11, 17, 5]$.

Example 4

The grader calls the function as follows:

find_spread(1, 2, [], [], [0, 0], [0, 0], [1000000000])

The function should return: $[0, 1000000000]$