La ville KOI a subi de lourds dommages pendant la pandémie de COVID-19 et souhaite se préparer soigneusement aux pandémies futures éventuelles. Elle veut pour cela analyser la vulnérabilité de sa structure actuelle face à un virus.

La ville KOI comprend $N$ lieux et $N-1$ routes bidirectionnelles, et deux lieux distincts quelconques sont reliés en empruntant uniquement des routes. Son réseau routier est donc un arbre. Les lieux portent des numéros entiers distincts de $0$ à $N-1$. Puisque le réseau est un arbre, il existe un unique chemin simple d’un lieu $u$ à un lieu $v$. La distance entre $u$ et $v$ est définie comme le nombre d’arêtes de ce chemin.

La ville KOI compte $M$ habitants. Pour tout $0\le j\le M-1$, la personne $j$ habite au lieu $P[j]$ et peut visiter les lieux situés à une distance d’au plus $D[j]$ de celui-ci.

Les virologues de la ville modélisent la transmission entre deux personnes comme suit. Pour tout $0\le v\le N-1$, le lieu $v$ possède un temps de transmission entier strictement positif $C[v]$. Supposons que la personne $j$ soit infectée pour la première fois à l’instant $t$ et considérons la transmission à la personne $k$. Si les deux peuvent visiter le lieu $w$, c’est-à-dire si sa distance à $P[j]$ est au plus $D[j]$ et celle à $P[k]$ au plus $D[k]$, alors $w$ est un lieu intermédiaire de transmission.

S’il n’existe aucun lieu intermédiaire, la personne $k$ n’est pas infectée directement par $j$, mais une infection indirecte par d’autres personnes reste possible. Sinon, soit $x$ un lieu intermédiaire de temps de transmission minimal. Si la personne $k$ n’est pas encore infectée à l’instant $t+C[x]$, la personne $j$ l’infecte à cet instant. Le virus se propage ainsi pour toutes les paires de personnes distinctes $0\le j,k\le M-1$, $j\ne k$.

Dans ce modèle, les chercheurs veulent déterminer quand les autres sont infectés si la personne $0$ est infectée à l’instant $0$. Pour tout $0\le j\le M-1$, calculez l’instant de première infection de la personne $j$. Indiquez $-1$ si elle n’est jamais infectée.

Détails d'implémentation

Vous devez implémenter la fonction suivante.

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$ : nombre de lieux de la ville KOI.
• $M$ : nombre de personnes de la ville KOI.
• $A,B$ : tableaux de longueur $N-1$. Pour tout $0\le i\le N-2$, une route relie $A[i]$ à $B[i]$. Chaque route apparaît exactement une fois dans ces deux tableaux.
• $P,D$ : tableaux de longueur $M$. Pour tout $0\le j\le M-1$, la personne $j$ habite en $P[j]$ et peut visiter les lieux à distance d’au plus $D[j]$ de celui-ci.
• $C$ : tableau de longueur $N$. Pour tout $0\le v\le N-1$, le temps de transmission au lieu $v$ est $C[v]$.
• La fonction doit renvoyer un tableau $T$ de taille $M$. Pour tout $0\le j\le M-1$, $T[j]$ doit être l’instant de première infection de la personne $j$, ou $-1$ si elle n’est jamais infectée.
• Cette fonction est appelée exactement une fois par cas de test.

Vous ne devez appeler aucune fonction d’entrée ou de sortie, où que ce soit dans le code source soumis.

Contraintes

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

Sous-tâches

1. (5 points)

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

2. (8 points)

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

3. (27 points)

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

4. (5 points)

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

5. (8 points)

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

6. (47 points)

   • Aucune contrainte supplémentaire.

Exemples

Exemples 1

Considérons le cas où $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]$.

Le programme d’évaluation appelle la fonction comme suit.

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

Dans ce cas, le virus se propage comme suit.

• La personne $0$ est infectée à l’instant $0$.
• La personne $3$ est infectée à l’instant $5$ par la personne $0$, via le lieu $1$. (Le lieu $2$ peut aussi servir d’intermédiaire.)
• La personne $4$ est infectée à l’instant $16$ par la personne $0$, via le lieu $3$.
• La personne $1$ est infectée à l’instant $24$ par la personne $4$, via le lieu $5$.
• La personne $2$ n’est jamais infectée.

La fonction doit renvoyer $[0,24,-1,5,16]$.

Exemples 2

Le programme d’évaluation appelle la fonction comme suit.

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 fonction doit renvoyer $[0,24,10,5,16]$.

Exemples 3

Le programme d’évaluation appelle la fonction comme suit.

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 fonction doit renvoyer $[0,11,17,11,5,11,5,11,17,5]$.

Exemples 4

Le programme d’évaluation appelle la fonction comme suit.

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

La fonction doit renvoyer $[0,1000000000]$.

Programme d’évaluation d’exemple

Le programme d’évaluation d’exemple lit l’entrée au format suivant.

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

Le programme d’évaluation d’exemple affiche ce qui suit.

• Ligne $1+j\quad(0\le j\le M-1)$: l’élément d’indice $j$ du tableau renvoyé par find_spread.

Notez que le programme d’évaluation d’exemple peut différer de celui utilisé pour l’évaluation réelle.