#include <bits/stdc++.h>
#define FOR(x, a, b) for (int x = a; x <= b; ++x)
#define FOD(x, a, b) for (int x = a; x >= b; --x)
#define REP(x, a, b) for (int x = a; x < b; ++x)
#define DEBUG(X) { cout << #X << " = " << X << endl; }
#define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; }
#define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; }
using namespace std;
typedef long long LL;
typedef pair <int, int> II;
const int N = 5e5 + 10;
const LL INF = (LL)1e18;
const int LG = 19;
int n, s, t, q, timer;
int h[N], a[N], b[N], e[N], V[2 * N], lg[2 * N], x[N];
int spT[2 * N][LG + 2];
LL f[N], d[N];
vector <II> adj[N];
struct CD {
int cPar[N], c[N];
void Init() {
memset(cPar, -1, sizeof cPar);
DFS(1);
Centroid(1, -1, c[1], -2);
}
void DFS(int u, int par = -1) {
c[u] = 1;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue;
DFS(v, u);
c[u] += c[v];
}
}
void Centroid(int u, int par, int sz, int preC) {
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue;
if (c[v] * 2 > sz) {
Centroid(v, u, sz, preC);
return;
}
}
cPar[u] = preC;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first; if (cPar[v] != -1) continue;
DFS(v);
Centroid(v, u, c[v], u);
}
}
} CD;
void DFS(int u, int par = -1) {
V[++timer] = u; x[u] = timer;
REP(k, 0, adj[u].size()) {
int v = adj[u][k].first, w = adj[u][k].second;
if (v == par) continue;
d[v] = d[u] + w;
h[v] = h[u] + 1;
DFS(v, u);
V[++timer] = u;
}
}
void InitLCA() {
assert(timer < 2 * N);
FOR(i, 1, timer) spT[i][0] = V[i];
for (int j = 1; 1 << j <= timer; ++j)
for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
int x = spT[i][j - 1], y = spT[i + (1 << (j - 1))][j - 1];
if (h[x] < h[y]) spT[i][j] = x;
else spT[i][j] = y;
}
for (int i = 0; 1 << i <= timer; ++i) lg[1 << i] = i;
FOR(i, 1, timer) if (!lg[i]) lg[i] = lg[i - 1];
}
inline int Query(int l, int r) {
if (l > r) swap(l, r);
int k = lg[r - l + 1];
int x = spT[l][k], y = spT[r - (1 << k) + 1][k];
if (h[x] < h[y]) return x;
else return y;
}
inline int LCA(int u, int v) {
return Query(x[u], x[v]);
}
inline LL Dist(int u, int v) {
int w = LCA(u, v);
return d[u] + d[v] - 2LL * d[w];
}
void Init(int NN, int A[], int B[], int D[]) {
n = NN;
REP(i, 0, n - 1) {
int u = A[i], v = B[i], w = D[i];
++u; ++v;
adj[u].push_back(II(v, w));
adj[v].push_back(II(u, w));
}
FOR(i, 1, n) f[i] = INF;
DFS(1);
InitLCA();
CD.Init();
}
void Update(int u) {
int x = u, d = 0;
while (x != -2) {
f[x] = min(f[x], Dist(x, u));
x = CD.cPar[x];
++d;
}
assert(d <= 20);
}
void Assign(int u, LL v) {
int x = u;
while (x != -2) {
f[x] = v;
x = CD.cPar[x];
}
}
LL Query(int u) {
int x = u, d = 0; LL ans = INF;
while (x != -2) {
ans = min(ans, f[x] + Dist(x, u));
x = CD.cPar[x];
++d;
}
assert(d <= 20);
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
s = S; t = T;
LL ans = INF;
REP(i, 0, s) {
++X[i];
Update(X[i]);
}
REP(i, 0, t) {
++Y[i];
ans = min(ans, Query(Y[i]));
}
REP(i, 0, s) Assign(X[i], INF);
return ans;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // LOCAL
scanf("%d%d", &n, &q);
FOR(i, 0, n - 2) scanf("%d%d%d", &a[i], &b[i], &e[i]);
Init(n, a, b, e);
while (q--) {
int s, t; scanf("%d%d", &s, &t);
REP(i, 0, s) scanf("%d", &a[i]);
REP(i, 0, t) scanf("%d", &b[i]);
printf("%lld\n", Query(s, a, t, b));
}
return 0;
}
Compilation message
factories.cpp: In member function 'void CD::DFS(int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:36:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp: In member function 'void CD::Centroid(int, int, int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:43:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:51:9: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp: In function 'void DFS(int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define REP(x, a, b) for (int x = a; x < b; ++x)
^
factories.cpp:61:5: note: in expansion of macro 'REP'
REP(k, 0, adj[u].size()) {
^
factories.cpp: In function 'int main()':
factories.cpp:164:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
^
factories.cpp:165:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
FOR(i, 0, n - 2) scanf("%d%d%d", &a[i], &b[i], &e[i]);
^
factories.cpp:168:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int s, t; scanf("%d%d", &s, &t);
^
factories.cpp:169:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REP(i, 0, s) scanf("%d", &a[i]);
^
factories.cpp:170:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
REP(i, 0, t) scanf("%d", &b[i]);
^
/tmp/ccJGskXq.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccvAtRW8.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
