Universal Cup Judging System

Universal Cup

時間限制: 4.0 s 記憶體限制: 1024 MB 總分: 100 可 Hack ✓
统计

¿Cuántas personas pueden tener tanto éxito como wcysai?

La Empresa R es una empresa de imprimir dinero fundada por wcysai, con unos ingresos anuales de más de 100 millones. Hay $n$ empleados trabajando en la Empresa R, y cada empleado vive en una casa. Las casas de algunos empleados están conectadas mediante carreteras bidireccionales. Se garantiza que, partiendo de la casa de cualquier empleado, se puede llegar a la casa de cualquier otro empleado a través de las carreteras.

Los empleados se dividen en dos tipos: gerentes (tipo A) y trabajadores (tipo B). Un gerente trabaja $a$ horas al día, mientras que un trabajador trabaja $b$ horas al día. Obviamente, los trabajadores deben trabajar más tiempo que los gerentes, por lo que $a < b$. Cada empleado tiene una hora de inicio de trabajo $s_i$. Si este empleado necesita trabajar $m$ horas ($m = a$ o $m = b$), entonces su hora de finalización es $t_i = s_i + m$.

Sin embargo, los empleados nunca quieren ser los más explotados. Por lo tanto, cuando empiezan a trabajar, comprueban si alguno de sus vecinos (es decir, empleados cuyas casas están conectadas directamente por carreteras) ya ha empezado a trabajar. Del mismo modo, cuando terminan de trabajar, comprueban si alguno de sus vecinos aún no ha terminado de trabajar. Si ambas observaciones son positivas, se sentirán satisfechos. Formalmente, un empleado está satisfecho si y solo si existe un vecino cuya hora de inicio sea estrictamente anterior a la suya, y existe un vecino cuya hora de finalización sea estrictamente posterior a la suya (estos dos vecinos pueden ser la misma persona o personas diferentes). De lo contrario, el empleado estará insatisfecho porque sentirá que es el más explotado.

Ahora, como hábil asistente de wcysai, puedes organizar libremente la hora de inicio de cada empleado. Quieres programar a todos los empleados de forma razonable para minimizar el número de personas insatisfechas. Ten en cuenta que puedes asignar como horas de inicio cualquier número real no negativo (consulta el formato de salida para más detalles).

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), el número de casos de prueba.

Para cada caso de prueba, la primera línea contiene cuatro enteros no negativos $n$, $m$, $a$ y $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), que representan el número de empleados, el número de carreteras, las horas de trabajo de los gerentes y las horas de trabajo de los trabajadores, respectivamente.

La siguiente línea contiene una cadena de longitud $n$ formada únicamente por A y B. El $i$-ésimo carácter representa el tipo del $i$-ésimo empleado.

Las siguientes $m$ líneas contienen cada una dos enteros no negativos $u, v$ ($1 \le u, v \le n$), que representan una carretera.

Se garantiza que si las casas de los empleados se consideran vértices y las carreteras aristas, el grafo no tiene aristas múltiples ni bucles, y es conexo.

Se garantiza que la suma de $n$ y la suma de $m$ en todos los casos de prueba no superan $5 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime una línea con $n$ enteros no negativos $s'_i$ ($0 \le s'_i \le 10^{18}$). Específicamente, sea $s_i$ la hora en que el $i$-ésimo empleado comienza a trabajar; entonces $s_i = \frac{s'_i}{10^6}$. Si existen múltiples horarios óptimos que minimizan el número de personas insatisfechas, imprime cualquiera de ellos.

Ejemplo

Entrada 1

5
2 1 1 5
AA
1 2
3 3 1 5
ABA
1 2
1 3
2 3
5 4 2 4
BABBB
1 2
1 5
2 3
2 4
6 9 1 5
BABBAB
1 2
1 3
1 4
2 6
3 4
3 5
3 6
4 5
5 6
7 7 2 5
BBAAABB
1 2
1 3
1 5
2 4
3 6
3 7
6 7

Salida 1

0 1
1 0 2
2 1 0 3 4
2 3 1 4 4000005 0
3000003 3000004 3000002 3000005 3000006 1 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.