No.902 Query ζone
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
Lemma299