#include <cstdio> #include <iostream> #include <ctime> #include <list> #include <queue> #include <stack> #include <vector> #include <set> #include <cstring> #include <string> #include <cmath> #include <algorithm> #include <cassert> using namespace std; class FastInput { public: FastInput() { } void init(int bufferLength) { this->bLen = bufferLength; this->b = new char[bufferLength]; fread(b, bufferLength, 1, stdin); this->bPos = 0; } ~FastInput() { delete this->b; } inline void readInt(int &r) { r = 0; // Skip non-digits while (bPos < bLen && (b[bPos] < '0' || b[bPos] > '9')) bPos++; // Read digits while (bPos < bLen && !(b[bPos] < '0' || b[bPos] > '9')) { r = 10 * r + b[bPos] - '0'; bPos++; } } private: int bLen, bPos; char* b; }; const int MAXN = 100005; const int maxn = 100005; const int MAXT = 1000005; const int maxlog = 18; const int logN = 17; int n, t; vector<int> edges[MAXN]; vector<int> costs[MAXN]; bool mark[MAXN]; int parent[MAXN]; int k; int vs[MAXT]; int tmpDfsOrder = 0; int dfsOrder[MAXN]; void initDfs(int u) { mark[u] = true; for (int i = 0; i < edges[u].size(); i++) { int v = edges[u][i]; if (!mark[v]) { parent[v] = u; initDfs(v); } } dfsOrder[tmpDfsOrder++] = u; } FastInput fin; void read_input() { #ifdef _DEBUG freopen("F:\\Test\\test.in", "r", stdin); #endif //freopen("F:\\Test\\test.in", "r", stdin); //freopen("sample.in", "r", stdin); fin.init(20000000); fin.readInt(n); fin.readInt(t); //scanf("%d%d", &n, &t); for (int i = 0; i < n - 1; i++) { int u, v, c; fin.readInt(u); fin.readInt(v); fin.readInt(c); //scanf("%d%d%d", &u, &v, &c); u--; v--; edges[u].push_back(v); costs[u].push_back(c); edges[v].push_back(u); costs[v].push_back(c); } parent[0] = -1; initDfs(0); memset(mark, 0, sizeof(mark)); } namespace dimi { // int level[maxn]; // long long sum[maxn][maxlog]; // int anc[maxn][maxlog]; // int parentEdgeCost[maxn]; // int parent[maxn]; int dfsnum[maxn]; // void dfs(int u, int anc, int lvl, int ancEdgeCost) { // parent[u] = anc; // parentEdgeCost[u] = ancEdgeCost; // level[u] = lvl; // // for (int i = 0, sz = edges[u].size(); i < sz; i++) { // int nodeAdj = edges[u][i]; // int costAdj = costs[u][i]; // // if (nodeAdj != anc) { // dfs(nodeAdj, u, lvl + 1, costAdj); // } // } // } int array[3 * maxn], sum[3 * maxn]; int arraypos[3 * maxn], greatest[3 * maxn]; int rmq[3 * maxn][maxlog]; int currDfsNum, currArrayPos = 0; void dfs(int u, int anc, int currSum, int ancEdgeCost) { dfsnum[u] = ++currDfsNum; arraypos[ dfsnum[u] ] = ++currArrayPos; array[currArrayPos] = dfsnum[u]; sum[ dfsnum[u] ] = currSum + ancEdgeCost; for (int i = 0, sz = edges[u].size(); i < sz; i++) { int nodeAdj = edges[u][i]; int costAdj = costs[u][i]; if (nodeAdj != anc) { dfs(nodeAdj, u, currSum + ancEdgeCost, costAdj); array[++currArrayPos] = dfsnum[u]; } } } const int inf = 1000000000; void initLca() { // memset(level, 0, sizeof(level)); // memset(parent, -1, sizeof(parent)); // dfs(0, -1, 0, 0); // // memset(anc, -1, sizeof(anc)); // memset(sum, 0, sizeof(sum)); // // for (int i = 0; i < n; i++) { // anc[i][0] = parent[i]; // sum[i][0] = parentEdgeCost[i]; // } // // for (int j = 1; j <= logN; j++) { // for (int i = 0; i < n; i++) { // sum[i][j] = sum[i][j - 1]; // if (anc[i][j - 1] != -1) { // anc[i][j] = anc[anc[i][j - 1]][j - 1]; // sum[i][j] += sum[anc[i][j - 1]][j - 1]; // } // } // } greatest[1] = 0; for (int i = 2; i <= 2 * n; i++) { if ((1 << greatest[i - 1] + 1) == i) { greatest[i] = greatest[i - 1] + 1; } else { greatest[i] = greatest[i - 1]; } } currDfsNum = 0; currArrayPos = 0; dfs(0, -1, 0, 0); for (int i = 1; i <= currArrayPos; i++) { rmq[i][0] = array[i]; } for (int j = 1; j <= logN; j++) { for (int i = 1; i <= currArrayPos; i++) { rmq[i][j] = min(rmq[i][j - 1], i + (1 << j - 1) > currArrayPos ? inf : rmq[i + (1 << j - 1)][j - 1]); } } } int rmq_min(int left, int right) { #ifdef DEBUG printf("left = %d right = %d\n", left, right); #endif if (left > right) { swap(left, right); } int st = greatest[right - left + 1]; int ret = min(rmq[left][st], rmq[right - (1 << st) + 1][st]); #ifdef DEBUG // for (int i = 1; i <= 10; i++) { // printf("greatest[%d] = %d\n", i, greatest[i]); // } printf("left = %d other = %d\n", left, right - (1 << st) + 1); printf("rmq[5][2] = %d rmq[6][2] = %d\n", rmq[5][2], rmq[6][2]); printf("st = %d\n", st); printf("ret = %d\n", ret); #endif return ret; } int getLca(int u, int v) { #ifdef DEBUG printf("u = %d v = %d\n", u, v); #endif return rmq_min(arraypos[ dfsnum[u] ], arraypos[ dfsnum[v] ]); } long long getDist(int u, int v) { // if (level[u] < level[v]) { // swap(u, v); // } // // long long ret = 0; // for (int i = logN; i >= 0; i--) { // if (level[u] - (1 << i) >= level[v]) { // ret += sum[u][i]; // u = anc[u][i]; // } // } // // if (u != v) { // for (int i = logN; i >= 0; i--) { // if (anc[u][i] != anc[v][i]) { // ret += sum[u][i] + sum[v][i]; // u = anc[u][i]; // v = anc[v][i]; // } // } // // ret += sum[u][0] + sum[v][0]; // } // // return ret; #ifdef DEBUG printf("currArrayPos = %d\n", currArrayPos); for (int i = 1; i <= currArrayPos; i++) { printf("%d ", array[i]); } printf("\n"); for (int i = 1; i <= n; i++) { printf("%d ", arraypos[i]); } printf("\n"); for (int i = 0; i < n; i++) { printf("i = %d dfsnum[i] = %d\n", i, dfsnum[i]); } printf("u = %d dfsnum[u] = %d v = %d dfsnum[v] = %d dfsnumlca = %d\n", u, dfsnum[u], v, dfsnum[v], getLca(u, v)); #endif int dfsnumlca = getLca(u, v); return sum[ dfsnum[u] ] + sum[ dfsnum[v] ] - 2 * sum[dfsnumlca]; } long long solve() { long long sol = 0; for (int i = 0; i < k; i++) { for (int j = i + 1; j < k; j++) { // debug(vs[i], vs[j], getDist(vs[i], vs[j])); sol += getDist(vs[i], vs[j]); } } return sol; } } namespace Smiljko { long long upC[MAXN]; int up[MAXN]; int residents[MAXN]; long long result; int childs[MAXN]; int eCosts[MAXN]; int start[MAXN]; void init() { int ind = 0; for (int i = 0; i < n; i++) { start[i] = ind; for (int j = 0; j < edges[i].size(); j++) { int v = edges[i][j]; if (v != parent[i]) { childs[ind] = v; eCosts[ind] = costs[i][j]; ind++; } } } start[n] = ind; } void iterate() { for (int it = 0; it < n; it++) { int u = dfsOrder[it]; up[u] = residents[u]; for (int i = start[u]; i < start[u + 1]; i++) { int v = childs[i]; up[u] += up[v]; } } for (int it = 0; it < n; it++) { int u = dfsOrder[it]; upC[u] = 0; if (up[u]) { for (int i = start[u]; i < start[u + 1]; i++) { int v = childs[i]; upC[u] += upC[v]; if (up[v]) upC[u] += eCosts[i] * up[v]; } } } for (int it = 0; it < n; it++) { int u = dfsOrder[it]; if (up[u] > 0) { for (int i = start[u]; i < start[u + 1]; i++) { int v = childs[i]; if (up[u] - up[v]) result += (upC[v] + eCosts[i] * up[v]) * (up[u] - up[v]); } } } } long long solve() { for (int i = 0; i < k; i++) { residents[vs[i]]++; } result = 0; iterate(); // dfs(0); for (int i = 0; i < k; i++) { residents[vs[i]]--; } return result; } } void read_task() { fin.readInt(k); // scanf("%d", &k); for (int i = 0; i < k; i++) { fin.readInt(vs[i]); //scanf("%d", vs + i); vs[i]--; } } void solve() { Smiljko::init(); dimi::initLca(); for (int __t = 0; __t < t; __t++) { read_task(); long long sol = -1; long long kk = k; // force smiljko if (kk * kk >= n) { // if (false) { //if (k > 500) { sol = Smiljko::solve(); } else { sol = dimi::solve(); } printf("%lld\n", sol); } } int main() { clock_t __starttime = clock(); read_input(); solve(); clock_t __endtime = clock(); fprintf(stderr, "time taken: %.2lfs\n", (double)(__endtime - __starttime) / CLOCKS_PER_SEC); return 0; }