問題一覧 > 通常問題

No.901 K-ary εxtrεεmε

レベル : / AI推定難易度 : 1975 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 82
作問者 : niuez / テスター : Lemma299 polylogK
お気に入りにしたユーザー ProblemId : 3407 / 自分の提出
問題文最終更新日: 2019-10-06 22:59:08
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もしくは右上の雲マークをクリックしてアカウントを作成してください。