Coloreando Geysers#11731
Una vez, Lucy encontró una cueva en uno de los planetas del sistema Link-Cut. La cueva consiste en salas y n - 1 pasajes; cada pasaje conecta dos salas, y es posible llegar a cualquier otra sala desde cualquier sala a través de los pasajes.
En cada sala, hay un géiser de color. Cuando el géiser de color en la sala número erupciona, colorea todas las salas que están a una distancia de no más de d_i de la sala en el color número . La distancia entre dos salas se define como el número mínimo de pasajes que necesitas recorrer para moverte entre ellas.
Lucy conoce la estructura de la cueva, los colores de algunas salas, y que cada géiser erupcionó exactamente una vez. Con base en esta información, determina cualquier orden posible en el que las erupciones podrían haber ocurrido.
La primera línea contiene un solo entero (2 \le n \le 10^5) — el número de salas en la cueva.
La segunda línea contiene enteros d_1, d_2, ... , d_n (0 \le d_i \le n - 1) — los parámetros de distancia de coloración para los géiseres.
La tercera línea contiene enteros c_1, c_2, ... , c_n (-1 \le c_i \le n), donde c_i es el número de color de la -ésima sala o , si el color de la -ésima sala es desconocido.
Las siguientes n - 1 líneas describen los pasajes. La -ésima línea contiene dos enteros u_i, v_i (1 \le u_i, v_i \le n, u_i \ne v_i) — las salas conectadas por el pasaje.
En una sola línea, imprime enteros p_1, p_2, ... , p_n, donde p_i es el número de la sala donde se encuentra el géiser que erupcionó en la -ésima. Se garantiza que hay al menos un orden que corresponde a los datos de entrada.
Ejemplo
Ejemplo 1
En el primer ejemplo, aquí están los colores de las salas después de cada erupción, asumiendo que sucedieron en el orden dado en la salida:
1, 1, 1, 1, 1
5, 1, 1, 1, 5
4, 1, 1, 4, 5
3, 1, 3, 4, 5
2, 2, 3, 4, 5
( puntos): n \le 8;
( puntos): d_i = 1 (1 \le i \le n);
( puntos): u_i = 1 (1 \le i \le n - 1);
( puntos): n \le 5 \cdot 10^4;
( puntos): sin restricciones adicionales.