No.650 行列木クエリ

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 37
作問者 : はむこはむこ / テスター : tanzakutanzaku
3 ProblemId : 1317 / 出題時の順位表

問題文

頂点$n$からなる木が与えられる。
頂点には番号$i (0 \leq i < n)$がついている。根は$0$である。
辺には番号$i (0 \leq i < n-1)$がついており、辺$i$は頂点$a_i$と頂点$b_i$を繋ぐ。

各辺$i$には、$2 \times 2$行列$X_i (0 \leq i < n-1)$が載っている。$X_i$の初期値は単位行列である。

以下のクエリを$q$個処理せよ。
(1) 変更クエリx
x $i\ x_{00}\ x_{01}\ x_{10}\ x_{11}$
$X_i (0 \leq i < n-1)$を$\begin{pmatrix} x_{00} & x_{01} \\ x_{10} & x_{11}\end{pmatrix}$に変更する。
(2) 取得クエリg
g $i\ j$
頂点$i$は頂点$j$の先祖であることが保証される。
頂点$i$から頂点$j$へのパスの辺に載っている行列を、すべて掛けた行列の各要素を$10^9+7$で割った出力する。
根側が左、葉側が右になるほうにかける。

入力

$n$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_{n-1}\ b_{n-1}$
$q$
$query_1$
$\vdots$
$query_q$

入力は全て整数。

$2 \leq n \leq 100000$
$1 \leq q \leq 20000$

クエリx
$0 \leq i < n-1$
$0 \leq x_{st} \leq 1000$

クエリg
$0 \leq i, j < n$

クエリgが$1$個以上あることが保証される。

出力

答えが$\begin{pmatrix} c_{00} & c_{01} \\ c_{10} & c_{11}\end{pmatrix}$であれば、
$c_{00}\ c_{01}\ c_{10}\ c_{11}$の順番で一行で出力せよ。

サンプル

サンプル1
入力
6
0 1
1 3
0 2
2 4
2 5
8
x 2 1 3 0 2
x 3 6 2 8 7
g 0 2
g 0 4
g 0 5
g 2 5
x 4 7 2 4 9
g 0 5
出力
1 3 0 2
30 23 16 14
1 3 0 2
1 0 0 1
19 29 8 18

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。