No.901 K-ary εxtrεεmε
問題文最終更新日: 2019-10-06 22:59:08
English (AI translation)
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 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.
The people living in niuez's town have recently grown tired of "Mitsukimono (three-tree things)". The latest trend is said to be "$K$-ary trees (Keki, i.e. cake)".
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$ queries ${\rm query}$.
-
$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_0, x_1, \cdots, x_{k_i-1}$ 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$
- For each ${\rm query}_i$:
- $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-1} k_i \le 10^5$
- All input values are integers
Output
Output $Q$ lines. On the $i$-th line, output the answer to the $i$-th ${\rm query}$ as an integer.
Sample
Sample 1
Input
7 0 1 1 0 2 2 1 3 3 1 4 4 2 5 5 2 6 6 5 3 0 1 2 3 0 3 4 3 3 5 6 4 3 4 5 6 2 3 6
Output
3 8 17 21 12
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Lemma299