La ciudad KOI sufrió grandes daños durante la pandemia de COVID-19 y quiere prepararse a fondo para posibles pandemias futuras. Para ello, quiere analizar la vulnerabilidad de su estructura actual frente a un virus.

La ciudad KOI consta de $N$ lugares y $N-1$ carreteras bidireccionales, y se puede viajar entre dos lugares distintos cualesquiera usando solo carreteras. Por tanto, su red de carreteras es un árbol. Los lugares tienen etiquetas enteras distintas de $0$ a $N-1$. Como la red es un árbol, existe un único camino simple de un lugar $u$ a un lugar $v$. La distancia entre $u$ y $v$ se define como el número de aristas de ese camino.

En la ciudad KOI viven $M$ personas. Para todo $0\le j\le M-1$, la persona $j$ vive en $P[j]$ y puede visitar lugares a distancia como máximo $D[j]$ de allí.

Los virólogos de la ciudad modelan la transmisión entre dos personas así. Para todo $0\le v\le N-1$, el lugar $v$ tiene un tiempo de transmisión entero positivo $C[v]$. Supón que la persona $j$ se infecta por primera vez en el instante $t$ y considera la transmisión a la persona $k$. Si ambas pueden visitar el lugar $w$, es decir, su distancia a $P[j]$ es como máximo $D[j]$ y a $P[k]$ es como máximo $D[k]$, entonces $w$ es un lugar intermediario de transmisión.

Si no hay lugar intermediario, la persona $k$ no se infecta directamente por $j$, aunque puede infectarse indirectamente a través de otras personas. En caso contrario, sea $x$ un lugar intermediario de tiempo de transmisión mínimo. Si la persona $k$ aún no está infectada en el instante $t+C[x]$, la persona $j$ la infecta en ese instante. El virus se propaga así para todos los pares de personas distintas $0\le j,k\le M-1$, $j\ne k$.

Bajo este modelo, los investigadores quieren saber cuándo se infectan los demás si la persona $0$ se infecta en el instante $0$. Para todo $0\le j\le M-1$, calcula el instante en que la persona $j$ se infecta por primera vez. Registra $-1$ si nunca se infecta.

Detalles de implementación

Debes implementar la siguiente función.

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$: número de lugares de la ciudad KOI.
• $M$: número de personas de la ciudad KOI.
• $A,B$: arreglos de longitud $N-1$. Para todo $0\le i\le N-2$, hay una carretera entre $A[i]$ y $B[i]$. Cada carretera aparece exactamente una vez en estos dos arreglos.
• $P,D$: arreglos de longitud $M$. Para todo $0\le j\le M-1$, la persona $j$ vive en $P[j]$ y puede visitar lugares a distancia como máximo $D[j]$ de allí.
• $C$: arreglo de longitud $N$. Para todo $0\le v\le N-1$, el tiempo de transmisión del lugar $v$ es $C[v]$.
• La función debe devolver un arreglo $T$ de tamaño $M$. Para todo $0\le j\le M-1$, $T[j]$ debe ser el primer instante de infección de la persona $j$, o $-1$ si nunca se infecta.
• La función se llama exactamente una vez por caso de prueba.

No debes llamar a funciones de entrada o salida en ninguna parte del código fuente enviado.

Restricciones

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

Subtareas

1. (5 puntos)

   • $N\le500$, $M\le500$.
   • Para todo $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

2. (8 puntos)

   • $N\le5\,000$, $M\le5\,000$.
   • Para todo $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

3. (27 puntos)

   • Para todo $0\le i\le N-2$, $A[i]=i$, $B[i]=i+1$.

4. (5 puntos)

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

5. (8 puntos)

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

6. (47 puntos)

   • Sin restricciones adicionales.

Ejemplos

Ejemplos 1

Considera el caso en que $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]$.

El evaluador llama a la función de la siguiente manera.

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

En este caso, el virus se propaga de la siguiente manera.

• La persona $0$ se infecta en el instante $0$.
• La persona $3$ se infecta en el instante $5$ por la persona $0$, con el lugar $1$ como intermediario. (El lugar $2$ también puede ser intermediario.)
• La persona $4$ se infecta en el instante $16$ por la persona $0$, con el lugar $3$ como intermediario.
• La persona $1$ se infecta en el instante $24$ por la persona $4$, con el lugar $5$ como intermediario.
• La persona $2$ nunca se infecta.

La función debe devolver $[0,24,-1,5,16]$.

Ejemplos 2

El evaluador llama a la función de la siguiente manera.

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

La función debe devolver $[0,24,10,5,16]$.

Ejemplos 3

El evaluador llama a la función de la siguiente manera.

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

La función debe devolver $[0,11,17,11,5,11,5,11,17,5]$.

Ejemplos 4

El evaluador llama a la función de la siguiente manera.

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

La función debe devolver $[0,1000000000]$.

Evaluador de ejemplo

El evaluador de ejemplo lee la entrada en el siguiente formato.

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

El evaluador de ejemplo imprime lo siguiente.

• Línea $1+j\quad(0\le j\le M-1)$: el elemento de índice $j$ del arreglo devuelto por find_spread.

Ten en cuenta que el evaluador de ejemplo puede diferir del utilizado en la evaluación real.