// I also thought that there was a small chance that she likes me back. #include <bits/stdc++.h> using namespace std; // Do you think you'll ever remember me someday, or will I just fade away from your memory? #define LIFESUCK ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define str string #define mll map<ll, ll> #define vll vector<ll> #define pll pair<ll, ll> #define fi first #define se second #define all(c) c.begin(), c.end() #define pb push_back #define sz(s) s.size() #define debug cout << "I Love You\n"; #define fu(i, a, b) for (ll i = a; i <= b; i++) #define fd(i, b, a) for (ll i = b; i >= a; i--) #define Bitc(msk, j) ((msk >> j) & 1) #define _log(x) 31 - __builtin_clz(x) #define LoveTime chrono::steady_clock::now().time_since_epoch().count() const ll Mod = 998244353; const ll inf = (1ll << 30); const ll lnf = (1ll << 60); // When time passes and things change... will you still remember someone like me? int64_t add(ll& a, ll b) { a += b; if (a >= Mod) a %= Mod; while (a < 0) a += Mod; return a; } int64_t mul(ll a, ll b) { a = 1ll * a * b % Mod; return a; } template <class X, class Y> bool minimize(X& x, Y y) { X eps = 1e-9; if (x > y + eps) { x = y; return 1; } return 0; } template <class X, class Y> bool maximize(X& x, Y y) { X eps = 1e-9; if (x + eps < y) { x = y; return 1; } return 0; } // I wonder… will I just become a distant memory to you one day? #define mxn 50'007 ll n, q, g[mxn]; ll dist[mxn]; ll f[19][mxn], h[mxn]; ll tin[mxn], tout[mxn], timeDfs = 0; vector<pll> graph[mxn], adj[mxn]; void dfsBuild(ll u) { tin[u] = ++timeDfs; for(auto&[v, w]: graph[u]) { if(v == f[0][u]) continue; f[0][v] = u; h[v] = h[u] + 1; dist[v] = dist[u] + w; fu(j, 1, 17) f[j][v] = f[j - 1][f[j - 1][v]]; dfsBuild(v); } tout[u] = timeDfs; } ll lca(ll u, ll v) { if(h[u] < h[v]) swap(u, v); ll k = (h[u] - h[v]); fu(j, 0, 17) if(Bitc(k, j)) u = f[j][u]; if(u == v) return u; fd(j, 17, 0) if(f[j][u] != f[j][v]) u = f[j][u], v = f[j][v]; return f[0][u]; } ll getDist(ll u, ll v) { ll p = lca(u, v); return dist[u] + dist[v] - 2 * dist[p]; } bool inside(ll u, ll v) { return (tin[u] <= tin[v] && tout[v] <= tout[u]); } void dfs(ll u, ll p) { for(auto&[v, w]: adj[u]) { if(v == p) continue; dfs(v, u); } } // The world is still beautiful, only it’s a pity that you are no longer among the living. void lovesper(const ll& TestCase) { cin >> n; fu(i, 2, n) { ll u, v, w; cin >> u >> v >> w; u++; v++; graph[u].pb({v, w}); graph[v].pb({u, w}); } dfsBuild(1); cin >> q; ll k = 5; fu(qst, 1, q) { vll c; c.pb(0); fu(i, 1, k) { ll u; cin >> u; c.pb(++u); } sort(all(c), [](ll u, ll v) {return tin[u] < tin[v]; }); fu(i, 2, k) c.pb(lca(c[i], c[i - 1])); sort(all(c), [](ll u, ll v) {return tin[u] < tin[v]; }); c.erase(unique(all(c)), c.end()); stack<ll> st; st.push(c[1]); ll sad = 0; fu(i, 2, sz(c) - 1) { while(!inside(st.top(), c[i])) st.pop(); sad += getDist(st.top(), c[i]); st.push(c[i]); } cout << sad << '\n'; for(auto&u: c) adj[u].clear(); } } // In the future, each of us will have our own path.. // ...But no matter where we go, we will always be a beautiful part of each other’s memories. signed main() { LIFESUCK #define name "lovesper" // freopen(name".inp", "r", stdin); // freopen(name".out", "w", stdout); ll Test = 1; // cin >> Test; fu(i, 1, Test) { lovesper(i); if (i < Test) cout << '\n'; } return 0; }