Tour JOI.

Points: 100 (partial)

Time limit: 7.0s

Memory limit: 1G

Authors:

FrankHG, eblabrada, Marco_Escandon

Problem type

Allowed languages

C++

En el país de JOI hay $N$ ~N~ pueblos, numerados del $1$ ~1~ al $N$ ~N~. Además, hay $N-1$ ~N-1~ carreteras en el país de JOI, también numeradas del $1$ ~1~ al $N-1$ ~N-1~. La carretera $j$ ~j~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~) conecta los pueblos $U_j$ ~U_j~ y $V_j$ ~V_j~ en ambas direcciones. Es posible viajar de cualquier pueblo a cualquier otro utilizando un número determinado de carreteras.

En cada pueblo del país de JOI hay una tienda. En la tienda del pueblo $i$ ~i~ ( $1 \leq i \leq N$ ~1 \leq i \leq N~), se vende un recuerdo por un precio $A_i$ ~A_i~. Este año, se han planificado $M$ ~M~ tours en el país de JOI. El $k-$ ~k-~ésimo tour ( $1 \leq k \leq M$ ~1 \leq k \leq M~) comienza en el pueblo $S_k$ ~S_k~ y viaja por carretera hasta el pueblo $T_k$ ~T_k~ sin pasar por el mismo pueblo dos veces. Cabe destacar que el $k-$ ~k-~ésimo tour visita los pueblos $S_k$ ~S_k~ y $T_k$ ~T_k~. Se garantiza que $S_k \neq T_k$ ~S_k \neq T_k~. Tenga en cuenta que, a partir de la estructura del país de JOI, la secuencia de ciudades que visita un tour está determinada de forma única.

Planea participar en uno de estos tours y comprar un recuerdo en cada una de exactamente dos de las ciudades que visitará. Además, desea utilizar exactamente todo el presupuesto destinado a recuerdos, por lo que, para cada uno de los $Q$ ~Q~ presupuestos candidatos, decidió investigar de cuántas maneras se puede lograr esto.

Dados los caminos del país de JOI, los precios de los recuerdos, la información sobre los tours y los presupuestos candidatos $B_1, B_2, ..., B_Q$ ~B_1, B_2, ..., B_Q~, escriba un programa que calcule el número de maneras de elegir un tour y las ciudades donde comprar recuerdos. Formalmente, para cada $q$ ~q~ ( $1 \leq q \leq Q$ ~1 \leq q \leq Q~), escriba un programa que calcule el número de tríos de enteros $(k, u, v)$ ~(k, u, v)~ que satisfacen todas las siguientes condiciones.

$1 \leq k \leq M$ ~1 \leq k \leq M~.
$1 \leq u < v \leq N$ ~1 \leq u < v \leq N~.
El $k-$ ~k-~ésimo tour visita las ciudades $u$ ~u~ y $v$ ~v~.
$A_u + A_v = B_q$ ~A_u + A_v = B_q~.

Entrada

La entrada es dada en el siguiente formato:

N
A_1 A_2 ··· A_N
U_1 V_1
U_2 V_2
...
U_N-1 V_N-1
M
S_1 T_1
S_2 T_2
...
S_M T_M
Q
B_1 B_2 ··· B_Q

Salida

Escriba $Q$ ~Q~ líneas en la salida estándar. La $q-$ ~q-~ésima línea $(1 \leq q \leq Q)$ ~(1 \leq q \leq Q)~ debe contener el número de maneras de elegir un tour y las ciudades donde comprar recuerdos para que el presupuesto $B_q$ ~B_q~ se utilice exactamente.

Restricciones

$2 \leq N \leq 100\,000$ ~2 \leq N \leq 100\,000~.
$1 \leq A_i \leq N$ ~1 \leq A_i \leq N~ ( $1 \leq i \leq N$ ~1 \leq i \leq N~).
$1 \leq U_j, V_j \leq N$ ~1 \leq U_j, V_j \leq N~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~).
Es posible viajar de cualquier ciudad a cualquier otra utilizando un número determinado de carreteras.
$1 \leq M \leq 200\,000$ ~1 \leq M \leq 200\,000~.
$1 \leq S_k, T_k \leq N$ ~1 \leq S_k, T_k \leq N~ ( $1 \leq k \leq M$ ~1 \leq k \leq M~), $S_k \neq T_k$ ~S_k \neq T_k~.
$1 \leq Q \leq 2000$ ~1 \leq Q \leq 2000~.
$1 \leq B_1 < B_2 < \ldots < B_Q \leq 2\cdot N$ .
Todos los valores de entrada son enteros.

Subtareas

Subtarea	Puntos	Restricciones adicionales
$1$ ~1~	$3$ ~3~	$N \leq 100$ ~N \leq 100~, $M \leq 100$ ~M \leq 100~, $Q \leq 100$ ~Q \leq 100~
$2$ ~2~	$4$ ~4~	$N \leq 5000$ ~N \leq 5000~, $U_j = j$ ~U_j = j~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~), $V_j = j+1$ ~V_j = j+1~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~)
$3$ ~3~	$5$ ~5~	$N \leq 5000$ ~N \leq 5000~
$4$ ~4~	$6$ ~6~	$Q = 1$ ~Q = 1~, $U_j = j$ ~U_j = j~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~), $V_j = j+1$ ~V_j = j+1~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~)
$5$ ~5~	$10$ ~10~	$Q = 1$ ~Q = 1~
$6$ ~6~	$7$ ~7~	$M \leq 1000$ ~M \leq 1000~, $U_j = j$ ~U_j = j~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~), $V_j = j+1$ ~V_j = j+1~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~)
$7$ ~7~	$12$ ~12~	$M \leq 1000$ ~M \leq 1000~
$8$ ~8~	$10$ ~10~	$N \leq 50\,000$ ~N \leq 50\,000~, $M \leq 50 000$ ~M \leq 50 000~, $U_j = j$ ~U_j = j~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~), $V_j = j+1$ ~V_j = j+1~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~)
$9$ ~9~	$15$ ~15~	$N \leq 50\,000$ ~N \leq 50\,000~, $M \leq 50 000$ ~M \leq 50 000~
$10$ ~10~	$11$ ~11~	$U_j = j$ ~U_j = j~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~), $V_j = j+1$ ~V_j = j+1~ ( $1 \leq j \leq N-1$ ~1 \leq j \leq N-1~)
$11$ ~11~	$17$ ~17~	Sin restricciones adicionales

Ejemplos

Entrada 1

8
1 2 3 2 1 2 3 2
2 3
7 8
4 3
1 2
7 3
2 5
6 1
4
1 4
1 6
2 5
3 8
7
1 2 3 4 5 6 16

Salida 1

A continuación se muestran las ciudades visitadas en cada tour.

El primer tour visita las ciudades $1, 2, 3$ ~1, 2, 3~ y $4$ ~4~.
El segundo tour visita las ciudades $1$ ~1~ y $6$ ~6~.
El tercer tour visita las ciudades $2$ ~2~ y $5$ ~5~.
El cuarto tour visita las ciudades $3, 7$ ~3, 7~ y $8$ ~8~.

Para cada presupuesto candidato, las formas de utilizarlo por completo son las siguientes:

No hay formas de utilizar exactamente el presupuesto $1$ ~1~.
No hay formas de utilizar exactamente el presupuesto $2$ ~2~.
Hay $4$ ~4~ formas de utilizar exactamente el presupuesto $3$ ~3~: $(1, 1, 2)$ ~(1, 1, 2)~, $(1, 1, 4)$ ~(1, 1, 4)~, $(2, 1, 6)$ ~(2, 1, 6)~, $(3, 2, 5)$ ~(3, 2, 5)~.
Hay $2$ ~2~ formas de utilizar exactamente el presupuesto $4$ ~4~: $(1, 1, 3)$ ~(1, 1, 3)~, $(1, 2, 4)$ ~(1, 2, 4)~.
Hay $4$ ~4~ maneras de utilizar exactamente el presupuesto $5$ ~5~: $(1, 2, 3)$ ~(1, 2, 3)~, $(1, 3, 4)$ ~(1, 3, 4)~, $(4, 3, 8)$ ~(4, 3, 8)~, $(4, 7, 8)$ ~(4, 7, 8)~.
Hay $1$ ~1~ manera de utilizar exactamente el presupuesto $6$ ~6~: $(4, 3, 7)$ ~(4, 3, 7)~.
No hay formas de utilizar exactamente el presupuesto $16$ ~16~.

Nota: Este ejemplo satisface las restricciones de las subtareas $1, 3, 7, 9, 11$ ~1, 3, 7, 9, 11~.

Entrada 2

8
8 2 3 6 1 4 1 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8 
1
1 8
5
2 4 5 10 15

Salida 2

Nota: Este ejemplo satisface las restricciones de las subtareas $1, 2, 3, 6, 7, 8, 9, 10, 11$ ~1, 2, 3, 6, 7, 8, 9, 10, 11~.

Comments

There are no comments at the moment.