// This solution is correct // O(knlgn + k^2 q) (Should AC) // Exported by Exporter.exe // Included from Fast.cpp // Compile flags -Wall -Wextra -Wshadow -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -fmax-errors=2 #include using namespace std; #define PB push_back #define F first #define S second #define MP make_pair #define MTP make_tuple typedef long long int ll; constexpr int kN = int(1E5 + 10); constexpr int kLgn = 17; // constexpr int kMod = 998244353; // constexpr int kInf = 0x3f3f3f3f; constexpr ll kInf = 0x3f3f3f3f3f3f3f3f; // constexpr double kPi = acos(-1); // constexpr double kEps = 1E-9; template T ABS(T n) {return n >= 0 ? n : -n;} // Included from C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cpp static inline char Get_Raw_Char() { static char buf[1 << 16], *p = buf, *end = buf; if (p == end) { if ((end = buf + fread(buf, 1, 1 << 16, stdin)) == buf) return '\0'; p = buf; } return *p++; } static inline int Get_Digit() { char c = Get_Raw_Char(); while (!isdigit(c)) c = Get_Raw_Char(); return int(c - '0'); } static inline int Get_PInt() { char c = Get_Raw_Char(); int ret; while (!isdigit(c)) c = Get_Raw_Char(); ret = int(c - '0'); while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0'); return ret; } static inline int Get_Int() { char c = Get_Raw_Char(); bool neg = false; int ret; while (!isdigit(c)) { if (c == '-') neg = true; c = Get_Raw_Char(); } ret = int(c - '0'); while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0'); if (neg) return -ret; return ret; } static inline long long int Get_ll() { char c = Get_Raw_Char(); bool neg = false; long long int ret; while (!isdigit(c)) { if (c == '-') neg = true; c = Get_Raw_Char(); } ret = int(c - '0'); while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0'); if (neg) return -ret; return ret; } static inline long long int Get_Pll() { char c = Get_Raw_Char(); long long int ret; while (!isdigit(c)) c = Get_Raw_Char(); ret = int(c - '0'); while (isdigit(c = Get_Raw_Char())) ret = ret * 10 + int(c - '0'); return ret; } template static inline void Read_P(T &n) { static_assert(is_integral::value); char c = Get_Raw_Char(); while (!isdigit(c)) c = Get_Raw_Char(); n = int(c - '0'); while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0'); return ; } template static inline void Read(T &n) { static_assert(is_integral::value); char c = Get_Raw_Char(); bool neg = false; while (!isdigit(c)) { if (c == '-') neg = true; c = Get_Raw_Char(); } n = int(c - '0'); while (isdigit(c = Get_Raw_Char())) n = n * 10 + int(c - '0'); if (neg) n = -n; return ; } template static inline void Read_Digit(T &n) { static_assert(is_integral::value); char c = Get_Raw_Char(); while (!isdigit(c)) c = Get_Raw_Char(); n = int(c - '0'); return ; } template static inline void Read(T &n, Targs&... Fargs) { Read(n); return Read(Fargs...); } template static inline void Read_Digit(T &n, Targs&... Fargs) { Read_Digit(n); return Read_Digit(Fargs...); } template static inline void Read_P(T &n, Targs&... Fargs) { Read_P(n); return Read_P(Fargs...); } // End of C:\Users\ianli\Desktop\CP\template\Various\Fast_IO.cpp int m[10], p[10], x[10][kN], u[kN], v[kN], dep[kN]; ll ans[kN], fa[kLgn][kN], dis[10][kN], dis_color[10][10]; vector> graph[kN]; bitset went; void dfs(int cur, int from) { for (pair i : graph[cur]) if (i.F != from) { fa[0][i.F] = cur; dis[0][i.F] = dis[0][cur] + i.S; dep[i.F] = dep[cur] + 1; dfs(i.F, cur); } return ; } int LCA(int l, int r) { if (dep[l] < dep[r]) swap(l, r); for (int i = kLgn - 1; i >= 0; i--) if (dep[fa[i][l]] >= dep[r]) l = fa[i][l]; if (l == r) return l; for (int i = kLgn - 1; i >= 0; i--) if (fa[i][l] != fa[i][r]) l = fa[i][l], r = fa[i][r]; return fa[0][l]; } int main() { //ios::sync_with_stdio(false); //cin.tie(0); //freopen("file_name", "r", stdin); //freopen("file_name", "w", stdout); //fstream input, output; //input.open("file_name", ios::in); //output.open("file_name", ios::out); int n, k, q; scanf("%d%d", &n, &k); for (int i = 2; i <= n; i++) { int l, r, c; scanf("%d%d%d", &l, &r, &c); graph[l].PB(MP(r, c)); graph[r].PB(MP(l, c)); } for (int i = 1; i <= k; i++) { scanf("%d%d", &m[i], &p[i]); for (int j = 1; j <= m[i]; j++) scanf("%d", &x[i][j]); } scanf("%d", &q); for (int i = 1; i <= q; i++) scanf("%d%d", &u[i], &v[i]); // could be done in O(n) (tarjan's LCA) // O(nlgn) memset(dis, 0x3f, sizeof(dis)); memset(dis_color, 0x3f, sizeof(dis_color)); dis[0][1] = 0; dfs(1, 1); fa[0][1] = 1; for (int i = 1; i < kLgn; i++) for (int j = 1; j <= n; j++) fa[i][j] = fa[i - 1][fa[i - 1][j]]; for (int i = 1; i <= q; i++) ans[i] = dis[0][u[i]] + dis[0][v[i]] - dis[0][LCA(u[i], v[i])] * 2; // O(k nlgn) for (int i = 1; i <= k; i++) { priority_queue, vector>, greater>> pq; for (int j = 1; j <= m[i]; j++) pq.push(MP(dis[i][x[i][j]] = 0, x[i][j])); while (!pq.empty()) { int cur = pq.top().S; ll ndis = pq.top().F; pq.pop(); if (ndis > dis[i][cur]) continue; for (pair j : graph[cur]) if (dis[i][j.F] > ndis + j.S) pq.push(MP(dis[i][j.F] = ndis + j.S, j.F)); } for (int j = i + 1; j <= k; j++) for (int c = 1; c <= m[j]; c++) dis_color[i][j] = min(dis_color[i][j], dis[i][x[j][c]]); } // O(k^3) for (int i = 1; i <= k; i++) dis_color[i][i] = 0; for (int i = 1; i <= k; i++) for (int j = i + 1; j <= k; j++) dis_color[j][i] = dis_color[i][j]; for (int c = 1; c <= k; c++) for (int i = 1; i <= k; i++) for (int j = 1; j <= k; j++) dis_color[i][j] = min(dis_color[i][j], dis_color[i][c] + dis_color[c][j] + p[c]); for (int i = 1; i <= k; i++) for (int j = 1; j <= k; j++) if (i == j) dis_color[i][j] += p[i]; else dis_color[i][j] += p[i] + p[j]; // O(k^2 q) for (int i = 1; i <= q; i++) for (int a = 1; a <= k; a++) for (int b = 1; b <= k; b++) ans[i] = min(ans[i], dis[a][u[i]] + dis[b][v[i]] + dis_color[a][b]); for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]); //input.close(); //output.close(); } // End of Fast.cpp