問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 78
作問者 : niuez / テスター : Lemma299 polylogK
3 ProblemId : 3407 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-10-06 22:59:08

注意

B問題(tri-βutree), E問題(K-ary εxtrεεmε), F問題(Query ζone) は順番に上位互換な問題になっています.

問題文

2019/10/4 21:46 B 問題と同様に問題文を修正しました．

niuez くんの街に住んでいる人は，最近「三つ木もの」に飽きてきました．最近の流行りは「K 木（ケーキ）」だそうです．

0 から N−1 までの番号のついた N 頂点，N−1 辺からなる無向木があり，i (0≤i<N−1) 番目の辺は頂点 ui と vi を端点とし，wi の重みを持っています．
以下の Q 個の query を処理してください．

  • ki x0 x1 ⋯ xki−1
    • 木の連結成分のうち，互いに異なる ki 個の頂点 x0,x1,⋯,xki−1 が含まれていて，かつ頂点数が最小であるような木の連結な部分グラフに含まれる辺の重みの総和を求める（2019/10/4 21:44 用語の誤りを修正しました）．．
    • このような木の部分グラフは一意に定まることが証明出来ます．

入力

N
u0 v0 w0
⋯
uN−2 vN−2 wN−2
Q
query0
⋯
queryQ−1
  • 2≤N≤105
  • 0≤ui,vi<N
    • ui≠vi
    • (ui,vi)=(uj,vj)⇔i=j
  • 0≤wi≤105
  • 1≤Q≤105
  • 各 queryi について
    • 1≤ki≤N
    • 0≤xj<N, (0≤j<ki)
    • x0, x1, ⋯,xki−1は互いに異なる
  • 1≤∑i=0Q−1ki≤105
  • 入力はすべて整数

出力

Q 行出力し，i 行目には i 番目の query の答えを整数で一行に出力してください．

サンプル

サンプル1
入力
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
出力
3
8
17
21
12

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