No.902 Query ζone

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.902 Query ζone

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 :

niuez / テスター :

Lemma299

polylogK

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$ 問目が作れて嬉しかったので意地悪に $q u e r y$ を増やしてしまいました．

はじめ， $0$ から $N - 1$ までの番号のついた $N$ 頂点， $N - 1$ 辺からなる無向木があり， $i (0 \leq i < N - 1)$ 番目の辺は頂点 $u_{i}$ と $v_{i}$ を端点とし， $w_{i}$ の重みを持っています．
以下の $Q$ 個の $q u e r y$ を処理してください．

$q u e r y 1$
```
 $1 u_{i} v_{i} w_{i} x_{i}$ 
```
- 木から辺 $u_{i} - v_{i}$ を削除し，新たに重み $x_{i}$ の辺 $v_{i} - w_{i}$ を追加する．
- このクエリの前後においてグラフが $N$ 頂点からなる無向木であることが保証されます．
$q u e r y 2$
```
 $2 k_{i} x_{0} x_{1} \dots x_{k_{i} - 1}$ 
```
- 木の連結成分のうち，互いに異なる $k_{i}$ 個の頂点 $x_{1}, x_{2}, \dots, x_{k_{i}}$ が含まれていて，かつ頂点数が最小であるような木の連結な部分グラフに含まれる辺の重みの総和を求める（2019/10/4 21:44 用語の誤りを修正しました）．
- このような木の部分グラフは一意に定まることが証明出来ます．

入力

 $N$ 
 $u_{0} v_{0} w_{0}$ 
 $\dots$ 
 $u_{N - 2} v_{N - 2} w_{N - 2}$ 
 $Q$ 
 ${q u e r y}_{0}$ 
 $\dots$ 
 ${q u e r y}_{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}$
各 ${q u e r y}_{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} \dots x_{k_{i} - 1}$ 
```
  - $1 \leq k_{i} \leq N$
  - $0 \leq x_{j} < N, (0 \leq j < k_{i})$
  - $x_{0}, x_{1}, \dots, x_{k_{i} - 1}$ は互いに異なる
$1 \leq \sum_{i = 0}^{Q} k_{i} \leq 10^{5}$
入力はすべて整数

出力

与えられた $q u e r y 2$ の個数行出力し， $i$ 行目には $i$ 番目の $q u e r y 2$ の答えを整数で一行に出力してください．

サンプル

サンプル1

入力

出力

20
27

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

yukicoder

No.902 Query ζone

注意

問題文

入力

出力

サンプル

サンプル1

入力

出力