問題一覧 > 通常問題

No.902 Query ζone

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : niuezniuez / テスター : Lemma299Lemma299 polylogKpolylogK
2 ProblemId : 3453 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-06 22:59:57

注意

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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。