Die Stadt KOI erlitt während der COVID-19-Pandemie große Schäden und möchte sich gründlich auf mögliche künftige Pandemien vorbereiten. Dazu möchte sie untersuchen, wie anfällig ihre derzeitige Stadtstruktur für ein Virus ist.

Die Stadt KOI besteht aus $N$ Orten und $N-1$ Straßen, die in beide Richtungen befahren werden können. Zwischen je zwei verschiedenen Orten kann man ausschließlich über Straßen reisen. Das Straßennetz ist also ein Baum. Die Orte tragen verschiedene ganzzahlige Nummern von $0$ bis $N-1$. Da das Netz ein Baum ist, gibt es von Ort $u$ zu Ort $v$ genau einen einfachen Pfad. Die Entfernung zwischen $u$ und $v$ ist die Anzahl seiner Kanten.

In der Stadt KOI leben $M$ Personen. Für alle $0\le j\le M-1$ wohnt Person $j$ am Ort $P[j]$ und kann Orte besuchen, deren Entfernung von dort höchstens $D[j]$ beträgt.

Die Virologen der Stadt modellieren die Übertragung zwischen zwei Personen wie folgt. Für alle $0\le v\le N-1$ hat Ort $v$ die positive ganzzahlige Übertragungszeit $C[v]$. Angenommen, Person $j$ infiziert sich erstmals zum Zeitpunkt $t$, und die Übertragung zu Person $k$ wird betrachtet. Können beide Ort $w$ besuchen, das heißt, ist seine Entfernung von $P[j]$ höchstens $D[j]$ und von $P[k]$ höchstens $D[k]$, so ist $w$ ein Vermittlungsort der Übertragung.

Gibt es keinen Vermittlungsort, infiziert Person $j$ die Person $k$ nicht direkt, eine indirekte Infektion über andere ist jedoch möglich. Andernfalls sei $x$ ein Vermittlungsort mit minimaler Übertragungszeit. Ist Person $k$ zum Zeitpunkt $t+C[x]$ noch nicht infiziert, wird sie dann durch Person $j$ infiziert. Das Virus verbreitet sich auf diese Weise für alle Paare verschiedener Personen $0\le j,k\le M-1$, $j\ne k$.

In diesem Modell wollen die Forscher die Infektionszeitpunkte der anderen Personen bestimmen, wenn Person $0$ zum Zeitpunkt $0$ infiziert wird. Berechne für alle $0\le j\le M-1$ den Zeitpunkt der ersten Infektion von Person $j$. Trage $-1$ ein, falls sie sich nie infiziert.

Implementierungsdetails

Du musst die folgende Funktion implementieren.

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

• $N$: die Anzahl der Orte in der Stadt KOI.
• $M$: die Anzahl der Personen in der Stadt KOI.
• $A,B$: Arrays der Länge $N-1$. Für alle $0\le i\le N-2$ verbindet eine Straße die Orte $A[i]$ und $B[i]$. Jede Straße erscheint in diesen beiden Arrays genau einmal.
• $P,D$: Arrays der Länge $M$. Für alle $0\le j\le M-1$ wohnt Person $j$ in $P[j]$ und kann Orte in einer Entfernung von höchstens $D[j]$ von dort besuchen.
• $C$: ein Array der Länge $N$. Für alle $0\le v\le N-1$ beträgt die Übertragungszeit an Ort $v$ genau $C[v]$.
• Die Funktion muss ein Array $T$ der Größe $M$ zurückgeben. Für alle $0\le j\le M-1$ muss $T[j]$ der Zeitpunkt der ersten Infektion von Person $j$ sein, oder $-1$, wenn sie nie infiziert wird.
• Diese Funktion wird pro Testfall genau einmal aufgerufen.

Im gesamten eingereichten Quellcode dürfen keine Ein- oder Ausgabefunktionen aufgerufen werden.

Beschränkungen

• $1\le N\le100\,000$
• $1\le M\le100\,000$
• Für alle $0\le i\le N-2$, $0\le A[i],B[i]\le N-1$, $A[i]\ne B[i]$.
• Für alle $0\le j\le M-1$, $0\le P[j],D[j]\le N-1$.
• Für alle $0\le v\le N-1$, $1\le C[v]\le10^9$.

Teilaufgaben

1. (5 Punkte)

   • $N\le500$, $M\le500$.
   • Für alle $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

2. (8 Punkte)

   • $N\le5\,000$, $M\le5\,000$.
   • Für alle $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

3. (27 Punkte)

   • Für alle $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

4. (5 Punkte)

   • $N\le500$, $M\le500$.

5. (8 Punkte)

   • $N\le5\,000$, $M\le5\,000$.

6. (47 Punkte)

   • Keine zusätzlichen Beschränkungen.

Beispiele

Beispiele 1

Betrachte den Fall mit $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]$, $C=[40,5,5,16,32,8,1,10]$.

Das Bewertungsprogramm ruft die Funktion wie folgt auf.

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 diesem Fall verbreitet sich das Virus wie folgt.

• Person $0$ wird zum Zeitpunkt $0$ infiziert.
• Person $3$ wird zum Zeitpunkt $5$ durch Person $0$ infiziert, wobei Ort $1$ vermittelt. (Auch Ort $2$ kann vermitteln.)
• Person $4$ wird zum Zeitpunkt $16$ durch Person $0$ infiziert, wobei Ort $3$ vermittelt.
• Person $1$ wird zum Zeitpunkt $24$ durch Person $4$ infiziert, wobei Ort $5$ vermittelt.
• Person $2$ wird niemals infiziert.

Die Funktion muss zurückgeben: $[0,24,-1,5,16]$.

Beispiele 2

Das Bewertungsprogramm ruft die Funktion wie folgt auf.

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])

Die Funktion muss zurückgeben: $[0,24,10,5,16]$.

Beispiele 3

Das Bewertungsprogramm ruft die Funktion wie folgt auf.

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])

Die Funktion muss zurückgeben: $[0,11,17,11,5,11,5,11,17,5]$.

Beispiele 4

Das Bewertungsprogramm ruft die Funktion wie folgt auf.

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

Die Funktion muss zurückgeben: $[0,1000000000]$.

Beispiel-Bewertungsprogramm

Das Beispiel-Bewertungsprogramm liest die Eingabe im folgenden Format.

• Zeile $1$: $N\ M$.
• Zeile $2+i\quad(0\le i\le N-2)$: $A[i]\ B[i]$.
• Zeile $1+N+j\quad(0\le j\le M-1)$: $P[j]\ D[j]$.
• Zeile $1+N+M$: $C[0]\ C[1]\ \ldots\ C[N-1]$.

Das Beispiel-Bewertungsprogramm gibt Folgendes aus.

• Zeile $1+j\quad(0\le j\le M-1)$: das Element mit Index $j$ des von find_spread zurückgegebenen Arrays.

Beachte, dass das Beispiel-Bewertungsprogramm vom tatsächlich verwendeten Bewertungsprogramm abweichen kann.