Universal Cup Judging System

Universal Cup

حد الوقت: 4.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

wcysai のように成功できる人間がどれほどいるでしょうか?

R 社は wcysai によって設立された、年間売上高 1 億を超える紙幣印刷のような会社です。R 社では $n$ 人の従業員が働いており、各従業員はそれぞれの家に住んでいます。一部の従業員の家同士は双方向の道路で結ばれています。どの従業員の家から出発しても、道路を通って他の任意の従業員の家に到達できることが保証されています。

従業員はマネージャー(タイプ A)と労働者(タイプ B)の 2 種類に分けられます。マネージャーは 1 日に $a$ 時間働き、労働者は 1 日に $b$ 時間働きます。明らかに労働者はマネージャーより長く働かなければならないため、$a < b$ です。各従業員には勤務開始時刻 $s_i$ があります。この従業員が $m$ 時間($m = a$ または $m = b$)働く必要がある場合、その勤務終了時刻は $t_i = s_i + m$ となります。

しかし、従業員たちは自分が最も酷使されている人間だとは思いたくありません。そのため、仕事を始めるときに、自分の隣人(つまり、家が道路で直接結ばれている従業員)の誰かがすでに仕事を始めているかどうかを確認します。同様に、仕事を終えるときに、自分の隣人の誰かがまだ仕事を終えていないかどうかを確認します。これら両方の確認結果が肯定的であれば、その従業員は満足します。厳密には、ある従業員が満足するのは、開始時刻が自分より真に早い隣人が存在し、かつ終了時刻が自分より真に遅い隣人が存在する場合、およびその場合に限ります(これら 2 人の隣人は同一人物であっても別人であっても構いません)。そうでない場合、その従業員は自分が最も酷使されていると感じて不満を抱きます。

さて、wcysai の有能な助手であるあなたは、各従業員の勤務開始時刻を自由に決めることができます。すべての従業員のスケジュールを適切に組み、不満を抱く人の数を最小化したいと考えています。なお、開始時刻には任意の非負実数を割り当てることができます(詳細は出力形式を参照してください)。

入力

1 行目には、テストケースの個数を表す整数 $T$($1 \le T \le 10^5$)が与えられます。

各テストケースについて、最初の行には 4 つの非負整数 $n$, $m$, $a$, $b$($1 \le n, m \le 5 \cdot 10^5$, $1 \le a < b \le 10^6$)が与えられ、それぞれ従業員の人数、道路の本数、マネージャーの労働時間、労働者の労働時間を表します。

次の行には、A と B のみからなる長さ $n$ の文字列が与えられます。$i$ 番目の文字は $i$ 番目の従業員のタイプを表します。

続く $m$ 行には、それぞれ道路を表す 2 つの非負整数 $u, v$($1 \le u, v \le n$)が与えられます。

従業員の家を頂点、道路を辺とみなしたとき、グラフは多重辺や自己ループを持たず、連結であることが保証されます。

すべてのテストケースにおける $n$ の総和および $m$ の総和は $5 \cdot 10^5$ を超えないことが保証されます。

出力

各テストケースについて、$n$ 個の非負整数 $s'_i$($0 \le s'_i \le 10^{18}$)を 1 行に出力してください。具体的には、$i$ 番目の従業員が仕事を始める時刻を $s_i$ とすると、$s_i = \frac{s'_i}{10^6}$ です。不満を抱く人の数を最小化する最適なスケジュールが複数存在する場合は、そのうちのどれを出力しても構いません。

入出力例

入力 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

出力 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.