Virus Spread Simulation in KOI City

This problem is adapted from the 2024 International Information Olympiad Representative Student Selection Test - 2nd Selection problem T4 "Virus".

KOI City is prepared for future epidemics after the serious impact of the recent pandemic. The city consists of $N$ locations and $N-1$ bidirectional roads. The road network forms a tree, so there is a unique simple path (and thus a well–defined distance in number of edges) between any two locations. The locations are labeled from $0$ to $N-1$.

There are $M$ residents in the city. For each resident $j$ ($0 \le j \le M-1$), they live at location $P[j]$ and can reach any location within distance $D[j]$ from $P[j]$.

The virologists of KOI City have constructed a model for virus transmission between different people. For every two distinct residents $j$ and $k$, assume that resident $j$ gets infected at time $t$. To possibly infect resident $k$ directly from resident $j$, there must exist a location $w$ such that:

• The distance from $P[j]$ to $w$ is at most $D[j]$.
• The distance from $P[k]$ to $w$ is at most $D[k]$.

If such locations exist, the virus uses the one with the smallest transmission time, i.e. the one with the minimum $C[w]$, as the medium. Then, if resident $k$ has not been infected before time $t+C[x]$, they will get infected at time $t+C[x]$, where $x$ is the chosen location. If no such location exists, resident $k$ cannot be infected directly from resident $j$ (though indirect infection through other residents is still possible).

Initially, resident $0$ is infected at time $0$. Your task is to compute for each resident $j$ the time at which they are first infected. If a resident is never infected, output -1.

Function Signature (for reference):

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

Here:

• $N$: Number of locations.
• $M$: Number of residents.
• $A$, $B$: Arrays of length $N-1$ representing the roads. For every $i$ ($0 \le i \le N-2$), there is a road connecting $A[i]$ and $B[i]$.
• $P$, $D$: Arrays of length $M$. Resident $j$ lives at location $P[j]$ and can reach locations within a distance $D[j]$ from $P[j]$.
• $C$: An array of length $N$. The transmission time at location $v$ ($0 \le v \le N-1$) is $C[v]$.

The function should return an array $T$ of length $M$ where $T[j]$ is the time when resident $j$ is first infected (or -1 if resident $j$ is never infected).

inputFormat

The input is given as follows:

N M
A[0] B[0]
A[1] B[1]
... (N-1 lines in total)
P[0] P[1] ... P[M-1]
D[0] D[1] ... D[M-1]
C[0] C[1] ... C[N-1]

Here, the first line contains two integers $N$ and $M$. The next $N-1$ lines each contain two integers representing a road between locations. Then follows a line with $M$ integers for the array $P$, a line with $M$ integers for the array $D$, and finally a line with $N$ integers for the array $C$.

outputFormat

Output a single line containing $M$ space‐separated integers. The $j$-th integer should be the time at which resident $j$ is first infected, or -1 if they are never infected.

sample

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

0 3