#P16239. [IIOT2026]Butea布泰亚

[IIOT2026]Butea布泰亚

题目描述

给定一棵有 nn 个顶点的带权二叉树,以及 qq 次询问。

第 ii 次询问给出:

  • 一个整数 kik_i;
  • 一个由 kik_i 个互不相同顶点组成的集合S={S1,S2,…,Ski}.S=\{S_1,S_2,\ldots,S_{k_i}\}.

你需要再选择一个恰好包含 kik_i 个顶点的集合

T={T1,T2,…,Tki}.T=\{T_1,T_2,\ldots,T_{k_i}\}.

TT 可以与 SS 有交集,甚至可以令 T=ST=S。

目标是最小化

$$\sum_{a=1}^{k_i}\sum_{b=1}^{k_i}\operatorname{dist}(S_a,T_b),$$

其中 dist⁡(u,v)\operatorname{dist}(u,v) 表示树上 u,vu,v 之间最短路径的长度。

输入格式

第一行包含两个整数 n,qn,q。

接下来 n−1n-1 行,每行包含三个整数 ui,vi,wiu_i,v_i,w_i,表示顶点 ui,viu_i,v_i 之间存在一条权值为 wiw_i 的边。

接下来 qq 行描述询问。每行先给出 kik_i,再给出 kik_i 个互不相同的顶点编号。

输出格式

对每次询问输出一行,表示最小可能值。

数据范围

  • 1≤n,q≤2⋅1051\le n,q\le2\cdot10^5;
  • 1≤wi≤101\le w_i\le10;
  • 所有询问的 kik_i 之和不超过 2⋅1052\cdot10^5;
  • 输入树可以选择某个根,使每个顶点至多有两个儿子。

子任务

子任务 分值 限制
1 0 样例
2 10 n,q≤200n,q\le200,∑ki≤400\sum k_i\le400
3 15 n,q≤2000n,q\le2000,∑ki≤4000\sum k_i\le4000
4 20 树是一条链
5 55 无额外限制

样例

输入

10 5
3 4 8
10 9 2
8 1 1
4 10 4
7 1 2
10 5 5
6 8 9
1 3 8
3 2 5
3 8 2 7
5 6 7 8 10 9
4 2 10 9 3
5 6 8 1 9 4
3 2 1 5

输出

51
306
128
280
103

样例中的树

第一问中,选择 T={1,8,7}T=\{1,8,7\} 时总代价为 5151。