#include <iostream> // strings/streams #include <string> #include <sstream> #include <vector> // datastructures #include <list> #include <set> #include <map> #include <queue> #include <stack> #include <bitset> #include <tuple> // quick compare #include <cstdio> // utils #include <numeric> #include <iterator> #include <algorithm> #include <cmath> #include <chrono> #include <cassert> #define REP(i,n) for(auto i = decltype(n)(0); i<(n); i++) #define F(v) begin(v), end(v) constexpr bool LOG = #ifdef _LOG true; #define _GLIBCXX_DEBUG #else false; #endif using namespace std; using ll = long long; using ii = pair<int,int>; using vi = vector<int>; using vb = vector<bool>; using vvi = vector<vi>; constexpr int INF = 1e9+1; // < 1e9 - -1e9 constexpr ll LLINF = 1e18+1; void Log() { if(LOG) cerr << "\n"; } template<class T, class... S> void Log(T t, S... s){ if(LOG) cerr << t << "\t", Log(s...); } /* ============== END OF HEADER ============== */ vi p; vvi childs; vector<ll> dr; struct E{int v; ll d;}; vector<vector<E>> edges; void dfs(int u, int par, ll droot){ p[u] = par; dr[u] = droot; for(auto e : edges[u]){ if(dr[e.v] < 0){ childs[u].push_back(e.v); dfs(e.v, u, droot + e.d); } } } struct HLD { int V,T; // Size; dfs-time; input parent/childs vi pr, size, heavy; // path-root; size of subtrees; heavy child vi t_in, t_out; // dfs in and out times HLD(int root = 0) : V(p.size()), T(0), pr(V,-1), size(V,-1), heavy(V,-1), t_in(V,-1), t_out(V,-1) { dfs(root); set_pr(root,0); } int dfs(int u){ size[u] = 1; t_in[u] = T++; int m = -1, mi = -1, s; // max, max index, size of subtree for(auto &v : childs[u]){ size[u] += s = dfs(v); if(s > m) m=s, mi = v; } heavy[u] = mi; t_out[u] = T++; return size[u]; } void set_pr(int u, int r){ // node, path root pr[u] = r; for(auto &v : childs[u]) set_pr(v, heavy[u] == v ? r : v); } bool is_parent(int p, int u){ // test whether p is a parent of u return t_in[p] <= t_in[u] && t_out[p] >= t_out[u]; } int lca(int u, int v){ while(!is_parent(pr[v],u)) v = p[pr[v]]; while(!is_parent(pr[u],v)) u = p[pr[u]]; return is_parent(u,v) ? u : v; } }; // return the number of K-nodes below node, and the total overcount pair<int,ll> dfs2(int u, const vector<vector<E>> &childs, const vi &count){ Log("visit",u, "nodes at u",count[u]); ll ans = 0; int child_count = count[u]; for(auto e : childs[u]){ Log("edge to",e.v,e.d); auto tmp = dfs2(e.v, childs, count); child_count += tmp.first; ans += tmp.second; ans += e.d * tmp.first * tmp.first; Log("childs ",tmp.first, " length", e.d," add ",e.d*2*tmp.first*tmp.first); } Log("return ",child_count, ans, "from ",u); return {child_count, ans}; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, T; cin >> N >> T; childs.resize(N); dr.resize(N,-1); p.resize(N, -1); edges.resize(N); REP(i,N-1){ // read edges int a,b,c; cin >> a >> b >> c; --a, --b; edges[a].push_back({b,c}); edges[b].push_back({a,c}); } // pre calculate the dfs-times and make the HLD for LCA queries // also, make the parent/childs representation dfs(0, -1, 0); Log("end dfs"); HLD hld; Log("creating HLD done"); // now, process all set-queries REP(tc,T){ int S; cin >> S; vector<int> K(S); // the set Log("process first set, with size",S, "members:"); REP(j,S) cin >> K[j], --K[j], Log(K[j]); ll ans = 0; for(auto u : K) ans += dr[u]; ans *= K.size(); Log("pre-ans:",ans); // sort the set on dfs-out-time sort(K.begin(), K.end(), [&](int l, int r){ return hld.t_out[l] < hld.t_out[r]; }); Log("sorted on finish time:"); //copy(F(K), ostream_iterator<int>(cerr," ")); //cerr << "\n"; // calculate lca's of neighbours vi in_tree(K); // add all nodes in K to the tree in_tree.push_back(0); // make sure the root is in the tree REP(i, K.size()-1){ in_tree.push_back(hld.lca(K[i], K[i+1])); Log("lca:",in_tree.back()); } // now sort everything together on out-time sort(in_tree.begin(), in_tree.end(), [&](int l, int r){ return hld.t_out[l] < hld.t_out[r]; }); Log("sorted on finish time:"); //copy(F(in_tree), ostream_iterator<int>(cerr," ")); //cerr << "\n"; // the new tree vector<vector<E>> t_childs; int t_size = 0; struct R{int u, t_u;}; // old index, and the index in the new tree stack<R> roots; map<int,int> m; for(auto &u : in_tree){ Log("visit ",u); // skip if already done if(!roots.empty() && u == roots.top().u) continue; // add u to the tree int t_u = t_size++; m[u] = t_u; t_childs.push_back({}); Log("add to root: t_u",t_u); // put old roots below u while(!roots.empty() && hld.is_parent(u, roots.top().u)){ // make u parent of roots.top() Log("set cur as parent of",roots.top().u, roots.top().t_u); t_childs[t_u].push_back({roots.top().t_u, dr[roots.top().u] - dr[u]}); Log("t_u has child",roots.top().t_u,"at distance ",dr[roots.top().u] - dr[u]); roots.pop(); } // and add u as new root roots.push({u,t_u}); Log("push new root",u,t_u); } assert(roots.size()==1); // the original parent should be a root of everything // bottom up dfs, subtract edge_size * childs^2 from answer for(auto u : m) Log("map:",u.first,u.second); vi t_count(t_size,0); for(auto u : K) t_count[m[u]]++; ans -= dfs2(roots.top().t_u, t_childs, t_count).second; cout << ans << "\n"; } return 0; }