題目背景
梦里鲜红的蔷薇 睁眼是苍白的玫瑰
題目描述
無限に広がる二分木の上に、一株のバラが絡みついています。その上には合計 $n$ 輪のバラが咲いており、根ノードを含む連結成分を構成しています。呪文は長さ $m$ の $01$ 文字列です。あるバラに対して呪文を唱えると、魔術回路が呪文に沿って下方に伝達されます。魔術回路は呪文の各文字に従って順に進み、文字が $0$ なら左の子へ、 $1$ なら右の子へ伝達されます。もし進むべき先にノードが存在しなければ、魔術は失敗します。すべてのバラについて、そのバラに対して呪文を唱えた場合に魔術が失敗するかどうか、成功した場合はどのバラに到達するかを求めてください。
入力
入力は以下の形式で与えられる。
$n$ $u_1 \ v_1 \ f_1$ $u_2 \ v_2 \ f_2$ $\vdots$ $u_{n-1} \ v_{n-1} \ f_{n-1}$ $m$ $S$
ここで、$n$ はバラの数である。続く $n-1$ 行は、$u$ から文字 $f$ を通じて $v$ へ伸びていることを表す。$m$ は呪文の長さであり、$S$ は長さ $m$ の $01$ 文字列である。
出力
$n$ 個の整数を一行に出力せよ。$i$ 番目の整数は、$i$ 番目のバラに対して呪文を唱えたときに到達するバラの番号を表す。魔術が失敗した場合は $0$ を出力せよ。
入出力例
入出力例 1
6 1 2 0 1 3 1 3 4 0 3 5 1 5 6 0 2 1 0
4 0 6 0 0 0
入出力例 2
(選手ディレクトリ内の rose/rose2.in および rose/rose2.ans を参照のこと)
制約
すべてのデータにおいて、$1 \le n, m \le 3 \times 10^5$、$1 \le u, v \le n$、$0 \le f \le 1$ を満たす。
| テストケース | $n, m$ | 特殊制限 |
|---|---|---|
| 1, 2, 3, 4 | $\le 10^3$ | |
| 5, 6, 7 | $\le 3 \times 10^5$ | A |
| 8, 9, 10 | $\le 3 \times 10^5$ |
特殊制限 A：各バラから下方に伸びる枝は最大で1本である。