/* -*- coding: utf-8 -*- * * 1442.cc: No.1442 I-wate Shortest Path Problem - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 100000; const int MAX_K = 10; const int BN = 17; // 2^17 = 131072 const long long LINF = 1LL << 62; /* typedef */ typedef long long ll; typedef pair pii; typedef pair pli; typedef vector vpii; /* global variables */ vpii nbrs[MAX_N + MAX_K]; int fcs[MAX_K]; int ps[MAX_N][BN], ds[MAX_N], cis[MAX_N]; ll pcs[MAX_N][BN], fds[MAX_K][MAX_N + MAX_K]; /* subroutines */ void dijkstra(int n, int st, ll ds[]) { fill(ds, ds + n, LINF); ds[st] = 0; priority_queue q; q.push(pli(0, st)); while (! q.empty()) { pli u = q.top(); q.pop(); ll ud = -u.first; int ui = u.second; if (ds[ui] != ud) continue; vpii &nbru = nbrs[ui]; for (vpii::iterator vit = nbru.begin(); vit != nbru.end(); vit++) { int vi = vit->first; ll vd = ud + vit->second; if (ds[vi] > vd) { ds[vi] = vd; q.push(pli(-vd, vi)); } } } } ll pathcost(int u, int v) { if (ds[u] > ds[v]) swap(u, v); ll c = 0; for (int i = BN - 1; i >= 0; i--) if (((ds[v] - ds[u]) >> i) & 1) c += pcs[v][i], v = ps[v][i]; if (u == v) return c; for (int i = BN - 1; i >= 0; i--) if (ps[u][i] != ps[v][i]) { c += pcs[u][i] + pcs[v][i]; u = ps[u][i], v = ps[v][i]; } return c + pcs[u][0] + pcs[v][0]; } /* main */ int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i < n; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); a--, b--; nbrs[a].push_back(pii(b, c)); nbrs[b].push_back(pii(a, c)); } for (int i = 0; i < k; i++) { int mi; scanf("%d%d", &mi, fcs + i); for (int j = 0; j < mi; j++) { int xj; scanf("%d", &xj); xj--; nbrs[n + i].push_back(pii(xj, 0)); nbrs[xj].push_back(pii(n + i, fcs[i])); } } for (int i = 0; i < k; i++) dijkstra(n + k, n + i, fds[i]); ps[0][0] = -1; pcs[0][0] = 0; ds[0] = 0; for (int u = 0; u >= 0;) { vpii &nbru = nbrs[u]; int up = ps[u][0]; if (cis[u] == 0) { for (int i = 0; i < BN - 1; i++) { if (ps[u][i] >= 0) { ps[u][i + 1] = ps[ps[u][i]][i]; pcs[u][i + 1] = pcs[u][i] + pcs[ps[u][i]][i]; } else { ps[u][i + 1] = -1; pcs[u][i + 1] = 0; } } } if (cis[u] < nbru.size()) { pii vv = nbru[cis[u]++]; int v = vv.first; if (v < n && v != up) { ps[v][0] = u; pcs[v][0] = vv.second; ds[v] = ds[u] + 1; u = v; } } else u = up; } int qn; scanf("%d", &qn); while (qn--) { int u, v; scanf("%d%d", &u, &v); u--, v--; ll minc = pathcost(u, v); //printf("pathcost(%d,%d) = %lld\n", u, v, minc); for (int i = 0; i < k; i++) { ll c = fds[i][u] + fds[i][v] + fcs[i]; if (minc > c) minc = c; } printf("%lld\n", minc); } return 0; }