#include<iostream> #include<algorithm> #include<vector> #define f first #define s second #define mp make_pair using namespace std; //Assumes root is 0 and the tree is connected template<int N> struct tree { vector<int> conn[N]; vector<int> cost[N]; int parent[N][20]; //This is the toposort data int arrayConstruct; int nodeInArray[N]; int arrayInNode[N]; int pointSpan[N]; int pointDist[N]; void addEdge(int a, int b, int curCost) { conn[a].push_back(b); cost[a].push_back(curCost); conn[b].push_back(a); cost[b].push_back(curCost); } //Initialize parent structure void dfsinit(int pos = 0, int curParent = -1, int curDistFromRoot = 0) { int cind = arrayConstruct++; //calculate parents parent[pos][0] = curParent; for(int i=1;i<20;i++) { if(parent[pos][i-1] == -1) parent[pos][i] = -1; else parent[pos][i] = parent[ parent[pos][i-1] ] [i-1]; } nodeInArray[pos] = cind; arrayInNode[cind] = pos; pointDist[cind] = curDistFromRoot; for(int i=0;i<conn[pos].size();i++) if(conn[pos][i] != curParent) { int next = conn[pos][i]; dfsinit(next, pos, curDistFromRoot + cost[pos][i]); } pointSpan[cind] = arrayConstruct; } //Calculate lowest subtree that contains both vertices int getSubtreeRoot(int a, int b) { if(nodeInArray[a] > nodeInArray[b]) swap(a, b); if(pointSpan[nodeInArray[a]] > nodeInArray[b]) return a; int ret = a; for(int i=19; i>=0; i--) { int par = parent[ret][i]; if(par == -1) continue; int parInArray = nodeInArray[par]; if(pointSpan[parInArray] <= nodeInArray[b]) ret = par; } return parent[ret][0]; } //Answers the question in an efficient manner int countArrs[N]; long long result; //format: (summary distance from root, number of people) pair<long long, int> solveWithIndices(vector<int> &inds, int& pos) { int cur = inds[pos++]; vector<pair<long long, int> > subs; pair<long long, int> ret = mp(0LL, 0); while(pos < inds.size() && inds[pos] < pointSpan[cur]) { long long cdist = pointDist[inds[pos]] - pointDist[cur]; pair<long long, int> cret = solveWithIndices(inds, pos); cret.f += cret.s * cdist; ret.f += cret.f; ret.s += cret.s; subs.push_back(cret); } ret.s += countArrs[cur]; //Finally we calculate the appropriate value to add to result for(int i=0;i<subs.size();i++) result += subs[i].f * (ret.s - subs[i].s); return ret; } //The basic solver funtion long long solve(vector<int> inds) { for(int i=0;i<inds.size();i++) { inds[i] = nodeInArray[inds[i]]; countArrs[inds[i]]++; } //Next we construct the subtree vector<int> subtree; for(int i=0;i<inds.size();i++) { subtree.push_back(inds[i]); } sort(inds.begin(), inds.end() ); for(int i=0;i + 1 < inds.size(); i++) { subtree.push_back( nodeInArray[getSubtreeRoot(arrayInNode[inds[i]], arrayInNode[inds[i+1]]) ] ); } //Clean the subtree indices sort(subtree.begin(), subtree.end() ); subtree.resize(unique(subtree.begin(), subtree.end() ) - subtree.begin() ); //Finally use the indices to solve the problem int pos = 0; result = 0; solveWithIndices(subtree, pos); //Do some cleanup for(int i=0;i<inds.size();i++) countArrs[inds[i]] = 0; return result; } }; //--------------------------------------------------------------------------------------------------- //tree structure ends here //Main function begins here //--------------------------------------------------------------------------------------------------- tree<100000> ct; int n, t, a, b, c; int main() { cin.sync_with_stdio(false); cin >> n >> t; for(int i=0;i<n-1;i++) { cin >> a >> b >> c; ct.addEdge(a-1, b-1, c); } ct.dfsinit(); //Answer the queries for(int i=0;i<t;i++) { cin >> a; vector<int> pts; for(int j=0;j<a;j++) { cin >> b; pts.push_back(b-1); } long long result = ct.solve(pts); cout << result << '\n'; } return 0; }