根付き木が与えられます。各ノードには脱出コスト $t_u$ があり、ノードから親へ移動するコストは $f_u$、子 $v$ へ移動するコストは $g_v$ です。
毎回 $u, k$ が与えられます。ノード $u$ から出発し、あるノード $v$ を選択して移動することを考えます。このとき、移動経路上のすべてのノードについて、根からの辺の数（深さ）が $k$ 以上である必要があります。この条件を満たしつつ、「$u$ から $v$ への移動コスト」と「$v$ での脱出コスト」の合計を最小化してください。クエリは非常に多いため、各クエリに対して最小の合計コストを答えてください。
入力
1行目に8つの非負整数 $n, m, \mathrm{SA}, \mathrm{SB}, \mathrm{SC}, t_1, t_2$ が与えられます。ここで $n$ は木のノード数、$m$ はクエリ数です。
続く1行に $n$ 個の非負整数 $t_i$ が与えられます。
続く $n - 1$ 行に、各行 $3$ つの整数 $p_i, f_i, g_i$ が与えられます。$i$ は $2$ から番号付けされ、$p_i$ は $i$ の親ノードです。$p_i < i$ であることが保証されます。
入出力の量を減らすため、クエリと出力は以下のコードによって生成されるものとします。ここで length[] 配列は、$i$ 番目の要素がノード $i$ から根までの辺の数であることを意味します。解決すべき部分は query() 関数です。メインプログラムで length[] 配列を処理した後、solve() 関数を一度呼び出すことができます。
unsigned int SA, SB, SC;
int n, m, t1, t2;
unsigned int rng61() {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
long long query(int u, int k);
void solve() {
long long lastans = 0, output = 0;
while (m--) {
int u = (rng61() ^ (t1 * lastans)) % n + 1;
int k = (rng61() ^ (t1 * lastans)) % (length[u] + 1) * t2;
lastans = query(u, k);
output ^= lastans + m;
}
printf("%lld\n", output);
}このコードは配布ファイル内の lyric/template.cpp に含まれています。
出力
上記の output 変数の値を出力してください。
入出力例
入力 1
10 10 629647033 688064407 427303738 1 1 8 7 16 11 7 20 18 9 16 6 1 3 13 2 8 11 3 12 3 4 20 3 5 10 14 3 19 8 7 9 8 8 12 18 6 10 10
出力 1
23
注記
このサンプルの各クエリと回答は以下の通りです。
4 2
10
1 0
8
6 2
16
10 6
6
6 4
16
6 0
16
6 2
16
6 3
16
10 0
6
1 0
8制約
$100\%$ のデータにおいて、$1\le n\le 3\times 10^5, 1\le m \le 6\times 10^6, 0\le t_1, t_2 \le 1$ であり、入力されるその他の整数は $0$ から $10^9$ の範囲です。
$0\%$ のデータにおいて、$m \le 5\times 10^7$ が保証されます。
| テストケース | $n$ | $m$ | $t_1$ | $t_2$ |
|---|---|---|---|---|
| $1$ | $=10$ | $=n$ | $0$ | $0$ |
| $2$ | $=10$ | $=n$ | $0$ | $1$ |
| $3$ | $=10$ | $=n$ | $1$ | $0$ |
| $4$ | $=10$ | $=n$ | $1$ | $1$ |
| $5$ | $=10^2$ | $=n$ | $0$ | $0$ |
| $6$ | $=10^2$ | $=n$ | $0$ | $1$ |
| $7$ | $=10^2$ | $=n$ | $1$ | $0$ |
| $8$ | $=10^2$ | $=n$ | $1$ | $1$ |
| $9$ | $=3,000$ | $=n$ | $0$ | $0$ |
| $10$ | $=3,000$ | $=n$ | $0$ | $1$ |
| $11$ | $=3,000$ | $=n$ | $1$ | $0$ |
| $12$ | $=3,000$ | $=n$ | $1$ | $1$ |
| $13$ | $=10^5$ | $=n$ | $0$ | $0$ |
| $14$ | $=10^5$ | $=n$ | $0$ | $1$ |
| $15$ | $=10^5$ | $=n$ | $1$ | $0$ |
| $16$ | $=10^5$ | $=n$ | $1$ | $1$ |
| $17$ | $=3\times 10^5$ | $=n$ | $0$ | $0$ |
| $18$ | $=3\times 10^5$ | $=n$ | $0$ | $1$ |
| $19$ | $=3\times 10^5$ | $=2\times10^6$ | $1$ | $0$ |
| $20$ | $=3\times 10^5$ | $=2\times10^6$ | $1$ | $1$ |
| $21,22$ | $=3\times 10^5$ | $=2\times10^6$ | $0$ | $1$ |
| $23,24$ | $=3\times 10^5$ | $=6\times10^6$ | $0$ | $1$ |
| $25$ | $=3\times 10^5$ | $=6\times10^6$ | $1$ | $1$ |
ストーリー
その童話のような時間は、あっという間に過ぎ去った。蘭は成長し、世界は変わってしまった。
空中楼閣を偽造するわけにはいかない。そうしたくはないが……事態はここまで来てしまった。私は彼女に「新しい世界」を見せなければならない。
茫然自失、驚愕。それが初めてそれを見た時の彼女の姿だった。私たちが千回も予行演習をしたにもかかわらず。
成長？いや、私は認めない！なぜ世界はこうでなければならないのか？なぜ世界はすべての夢を打ち砕くのか？そして、なぜ私は彼女を「無援と恐怖」の中に放り込まなければならないのか？
勘弁してくれ。私は平然を装うことも、大義名分を掲げてこれを「成長」などと呼ぶこともできない。
私は、戦争と憎しみの炎が彼女の瞳を燻すことを恐れている。
私は、無知という泥が彼女の清らかさを汚染することを恐れている。
私は、世間の氷柱が彼女の情熱を消し去ることを恐れている。
彼女は元の画室で一日中座り込み、かつて描いた星空をぼんやりと眺めていた。
翌日、彼女の髪が一本、白くなった。
「そんな芸術に……何の意味があるの！」
そう、絵を描くことは野蛮であり、詩を書くことも野蛮なのだ。
私はかつて彼女の十万の「なぜ」に答えてきた。しかし今日、私には答えがわからない。
あるいは、彼女にどう答えるべきかわからないのだ。私はただうつむき、歯を食いしばるしかなかった。
「……ごめんね」
その殿堂は轟音と共に崩れ去った。泉のように溢れ出しながら。
空の星々も血を流している。
私は蘭を連れて、この場所から去らなければならない。
そして、脱出する方法は、古のルーンの中にしか答えがない。
古の魔法のルーンシステムは非常に複雑で、文字の種類は数え切れないほどある。時間がないため、その詳細は省く。ただ、根付き木が一つ与えられると考えてほしい。根からあるノードへのパスは一つの文字列を表している。私が持ち歩いているルーンも、あるノード $u$ で表すことができる。木上の各ノードは私たちを脱出させてくれる。もし今持っているルーンがノード $u$ であれば、発動に $t_u$ の時間を消費する。しかし、持っているルーンは変更することもでき、それにも時間がかかる。ルーンの最後の文字を消す、つまりノード $u$ からその親へ移動するには $f_u$ の時間がかかり、ある子ノード $v$ へ移動するには $g_v$ の時間がかかる。
さらに制限がある。常に、文字列の長さが $k$ 未満になってはならない。文字列の長さとは、根ノードから現在地までの辺の数である。
君に頼みたいのは、最短時間で脱出する方法だ。複数の問題を出すかもしれない。時間がないので、できるだけ早く答えを教えてほしい。
歌詞
無趣な人生の中で、水しぶきを上げて、
花火とネオンの中で、夢想家になる、
逆光から来るシルエット、心拍が一瞬、
——「それは君だ。」
平坦な出会いの中で、時が芽吹き、
空っぽの教室で叫ぶ、声は枯れず、
私の瞳に映るすべての色彩、最も明るいのは、
——「君だけだ。」