問題一覧 > 通常問題

No.902 Query ζone

レベル : / AI推定難易度 : 3100 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 14
作問者 : niuez / テスター : Lemma299 polylogK
お気に入りにしたユーザー ProblemId : 3453 / 自分の提出
問題文最終更新日: 2019-10-06 22:59:57
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 226 (木上クエリコン) (順位表) の他の問題:

Note

Problem B (tri-βutree), Problem E (K-ary εxtrεεmε), Problem F (Query ζone) are problems in which each one is, in this order, a strict generalization of the previous one.

Problem Statement

2019/10/4 21:46 The problem statement was corrected in the same way as Problem B.

2019/10/6 22:53 The problem statement was corrected.

niuez was so happy to have managed to create a $5$th problem that he spitefully added more ${\rm query}$ types.

Initially, there is an undirected tree with $N$ vertices numbered from $0$ to $N-1$ and $N-1$ edges. The $i \ (0 \leq i < N-1)$-th edge has endpoints $u_i$ and $v_i$ and has weight $w_i$.
Process the following $Q$ ${\rm query}$s.

  • ${\rm query} 1$
    $1 \  u_i \  v_i \  w_i \  x_i$
    • Remove the edge $u_i-v_i$ from the tree, and add a new edge $v_i-w_i$ with weight $x_i$.
    • It is guaranteed that the graph is an undirected tree with $N$ vertices both before and after this query.
  • ${\rm query} 2$
    $2 \  k_i \  x_0 \  x_1 \  \cdots \  x_{k_i-1}$
    • Among the connected components of the tree, consider the connected subgraph of the tree that contains the $k_i$ pairwise distinct vertices $x_1, x_2, \cdots, x_{k_i}$ and has the minimum number of vertices, and find the sum of the weights of the edges it contains (2019/10/4 21:44 A terminology error was corrected).
    • It can be proved that such a subgraph of the tree is uniquely determined.

Input

$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$
  • Each ${\rm query}_i$ is one of the following:
    • $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}$ are pairwise distinct
  • $1 \le \sum_{i = 0}^Q k_i \le 10^5$
  • All input values are integers

Output

Output as many lines as there are given ${\rm query} 2$ queries. On the $i$-th line, output the answer to the $i$-th ${\rm query} 2$ as an integer on one line.

Sample

Sample 1
Input
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
Output
20
27

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