No.902 Query ζone

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 3
作問者 : niuezniuez / テスター : Lemma299Lemma299
1 ProblemId : 3453 / 出題時の順位表

注意

B問題(tri-βutree), E問題(K-ary εxtrεεmε), F問題(Query ζone) は順番に上位互換な問題になっています.

問題文

2019/10/4 21:46 B 問題と同様に問題文を修正しました.

2019/10/6 22:53 問題文を修正しました.

niuezくんは $5$ 問目が作れて嬉しかったので意地悪に ${\rm query}$ を増やしてしまいました.

はじめ,$0$ から $N-1$ までの番号のついた $N$ 頂点,$N-1$ 辺からなる無向木があり,$i \ (0 \leq i < N-1)$ 番目の辺は頂点 $u_i$ と $v_i$ を端点とし,$w_i$ の重みを持っています.
以下の $Q$ 個の ${\rm query}$ を処理してください.

  • ${\rm query} 1$
    $1 \  u_i \  v_i \  w_i \  x_i$
    • 木から辺 $u_i-v_i$ を削除し,新たに重み $x_i$ の辺 $v_i-w_i$ を追加する.
    • このクエリの前後においてグラフが $N$ 頂点からなる無向木であることが保証されます.
  • ${\rm query} 2$
    $2 \  k_i \  x_0 \  x_1 \  \cdots \  x_{k_i-1}$
    • 木の連結成分のうち,互いに異なる $k_i$ 個の頂点 $x_1, x_2, \cdots, x_{k_i}$ が含まれていて,かつ頂点数が最小であるような木の連結な部分グラフに含まれる辺の重みの総和を求める(2019/10/4 21:44 用語の誤りを修正しました).
    • このような木の部分グラフは一意に定まることが証明出来ます.

入力

$N$
$u_0 \  v_0 \  w_0$
$\cdots$
$u_{N-2} \  v_{N-2} \  w_{N-2}$
$Q$
${\rm query}_0$
$\cdots$
${\rm query}_{Q-1}$
  • $2 \leq N \leq 10^5$
  • $0 \leq u_i, v_i < N$
    • $u_i \neq v_i$
    • $(u_i, v_i) = (u_j, v_j) \Leftrightarrow i = j$
  • $0 \leq w_i \leq 10^5$
  • $1 \leq Q \leq 10^5$
  • 各 ${\rm query}_i$ は
    • $1 \  u_i \  v_i \  w_i \  x_i$
      • $0 \leq u_i, v_i, w_i < N$
      • $u_i \neq v_i$
      • $v_i \neq w_i$
      • $0 \leq x_i \leq 10^5$
    • $2 \  k_i \  x_0 \  x_1 \  \cdots \  x_{k_i-1}$
      • $1 \leq k_i \leq N$
      • $0 \leq x_j < N,\ (0 \le j < k_i)$
      • $x_0, \ x_1, \ \cdots, x_{k_i-1}$は互いに異なる
  • $1 \le \sum_{i = 0}^Q k_i \le 10^5$
  • 入力はすべて整数

出力

与えられた ${\rm query} 2$ の個数行出力し,$i$ 行目には $i$ 番目の ${\rm query} 2$ の答えを整数で一行に出力してください.

サンプル

サンプル1
入力
7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
4
1 1 4 5 7
2 3 0 4 6
1 0 2 1 8
2 3 0 4 6
出力
20
27

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

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