Universal Cup Judging System

Universal Cup

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

Berapa banyak orang yang bisa sesukses wcysai?

Perusahaan R adalah perusahaan pencetak uang yang didirikan oleh wcysai, dengan pendapatan tahunan lebih dari 100 juta. Terdapat $n$ karyawan yang bekerja di Perusahaan R, dan setiap karyawan tinggal di sebuah rumah. Beberapa rumah karyawan dihubungkan oleh jalan dua arah. Dijamin bahwa berangkat dari rumah karyawan mana pun, seseorang dapat mencapai rumah karyawan lainnya melalui jalan-jalan tersebut.

Karyawan dibagi menjadi dua jenis: manajer (jenis A) dan pekerja (jenis B). Seorang manajer bekerja selama $a$ jam per hari, sedangkan seorang pekerja bekerja selama $b$ jam per hari. Jelas bahwa pekerja harus bekerja lebih lama daripada manajer, sehingga $a < b$. Setiap karyawan memiliki waktu mulai kerja $s_i$. Jika karyawan ini harus bekerja selama $m$ jam ($m = a$ atau $m = b$), maka waktu selesai kerjanya adalah $t_i = s_i + m$.

Namun, para karyawan tidak pernah ingin menjadi orang yang paling diforsir kerjanya. Oleh karena itu, ketika mereka mulai bekerja, mereka akan memeriksa apakah ada tetangga mereka (yaitu karyawan yang rumahnya terhubung langsung oleh jalan) yang sudah mulai bekerja. Demikian pula, ketika mereka selesai bekerja, mereka akan memeriksa apakah ada tetangga mereka yang belum selesai bekerja. Jika kedua pengamatan tersebut positif, mereka akan merasa puas. Secara formal, seorang karyawan merasa puas jika dan hanya jika terdapat seorang tetangga yang waktu mulainya secara tegas lebih awal daripada waktu mulainya, dan terdapat seorang tetangga yang waktu selesainya secara tegas lebih akhir daripada waktu selesainya (kedua tetangga ini boleh orang yang sama maupun orang yang berbeda). Jika tidak, karyawan tersebut akan merasa tidak puas karena merasa dirinya adalah orang yang paling diforsir kerjanya.

Sekarang, sebagai asisten andalan wcysai, Anda bebas mengatur waktu mulai kerja setiap karyawan. Anda ingin menjadwalkan semua karyawan secara wajar sehingga banyaknya orang yang tidak puas dapat diminimalkan. Perhatikan bahwa Anda dapat menetapkan waktu mulai berupa bilangan riil non-negatif apa pun (lihat format keluaran untuk rinciannya).

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^5$), banyaknya kasus uji.

Untuk setiap kasus uji, baris pertama berisi empat bilangan bulat non-negatif $n$, $m$, $a$, dan $b$ ($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$), yang masing-masing menyatakan banyaknya karyawan, banyaknya jalan, jam kerja manajer, dan jam kerja pekerja.

Baris berikutnya berisi sebuah string sepanjang $n$ yang hanya terdiri dari A dan B. Karakter ke-$i$ menyatakan jenis karyawan ke-$i$.

$m$ baris berikutnya masing-masing berisi dua bilangan bulat non-negatif $u, v$ ($1 \le u, v \le n$), yang menyatakan sebuah jalan.

Dijamin bahwa jika rumah karyawan dianggap sebagai simpul dan jalan sebagai sisi, graf tersebut tidak memiliki sisi ganda maupun gelung (self-loop), serta terhubung.

Dijamin bahwa jumlah $n$ dan jumlah $m$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $n$ bilangan bulat non-negatif $s'_i$ ($0 \le s'_i \le 10^{18}$). Secara spesifik, misalkan $s_i$ menyatakan waktu ketika karyawan ke-$i$ mulai bekerja, maka $s_i = \frac{s'_i}{10^6}$. Jika terdapat beberapa jadwal optimal yang meminimalkan banyaknya orang yang tidak puas, keluarkan yang mana saja.

Contoh

Masukan 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

Keluaran 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.