#include using namespace std::literals::string_literals; using i64 = long long; using std::cout; using std::endl; using std::cin; template std::vector make_v(size_t a){return std::vector(a);} template auto make_v(size_t a,Ts... ts){ return std::vector(ts...))>(a,make_v(ts...)); } // build: you have to run it before you use // for_each: process [l, r] // for_each_edge: process [l, r] // distance: returns the dist (l, r) class heavy_light_decomposition { using size_type = size_t; using F = std::function; public: std::vector> g; std::vector vid, inv; private: std::vector head, sz, heavy, par, dep, type; void dfs(int root) { using P = std::pair; par[root] = -1; dep[root] = 0; std::stack

st; st.push({root, 0}); while(!st.empty()) { int v = st.top().first; int & i = st.top().second; if(i < g[v].size()) { int u = g[v][i++]; if(u == par[v]) continue; par[u] = v; dep[u] = dep[v] + 1; st.push({u, 0}); } else { st.pop(); int tmp = 0; for(auto e: g[v]) { if(e == par[v]) continue; sz[v] += sz[e]; if(tmp < sz[e]) { tmp = sz[e]; heavy[v] = e; } } } } } void bfs(int root, int c, int & k) { std::queue qu({root}); while(!qu.empty()) { int h = qu.front(); qu.pop(); for(int v = h; v != -1; v = heavy[v]) { type[v] = c; vid[v] = k++; inv[vid[v]] = v; head[v] = h; for(int e: g[v]) if(e != par[v] and e != heavy[v]) qu.push(e); } } } public: heavy_light_decomposition() {} heavy_light_decomposition(int n) : g(n), vid(n, -1), head(n), sz(n, 1), heavy(n, -1), par(n), dep(n), inv(n), type(n) {} void add_edge(int a, int b) { g[a].push_back(b); g[b].push_back(a); } void build(std::vector rs = std::vector(1, 0)) { int c = 0, k = 0; for(int r: rs) { dfs(r); bfs(r, c++, k); } } int lca(int u, int v) { while(true) { if(vid[u] > vid[v]) std::swap(u, v); if(head[u] == head[v]) return u; v = par[head[v]]; } } void for_each(int u, int v, const F & f) { while(true) { if(vid[u] > vid[v]) std::swap(u, v); f(std::max(vid[head[v]], vid[u]), vid[v]); if(head[u] != head[v]) v = par[head[v]]; else break; } } void for_each_edge(int u, int v, const F & f) { while(true) { if(vid[u] > vid[v]) std::swap(u, v); if(head[u] != head[v]) { f(vid[head[v]], vid[v]); v = par[head[v]]; } else { if(u != v) f(vid[u] + 1, vid[v]); break; } } } int distance(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } }; using namespace std; template struct SegmentTree{ using F = function; using G = function; using H = function; int n,height; F f; G g; H h; T ti; E ei; vector dat; vector laz; SegmentTree(F f,G g,H h,T ti,E ei): f(f),g(g),h(h),ti(ti),ei(ei){} void init(int n_){ n=1;height=0; while(n &v){ int n_=v.size(); init(n_); for(int i=0;i>i); } inline void recalc(int k){ while(k>>=1) dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1)); } void update(int a,int b,E x){ thrust(a+=n); thrust(b+=n-1); for(int l=a,r=b+1;l>=1,r>>=1){ if(l&1) laz[l]=h(laz[l],x),l++; if(r&1) --r,laz[r]=h(laz[r],x); } recalc(a); recalc(b); } void set_val(int a,T x){ thrust(a+=n); dat[a]=x;laz[a]=ei; recalc(a); } T query(int a,int b){ thrust(a+=n); thrust(b+=n-1); T vl=ti,vr=ti; for(int l=a,r=b+1;l>=1,r>>=1) { if(l&1) vl=f(vl,reflect(l++)); if(r&1) vr=f(reflect(--r),vr); } return f(vl,vr); } }; struct node { int used; int depth; int label; int depth_all; int label_all; node() : used(1), depth(-1), label(-1), depth_all(-1), label_all(-1) {} node(int used, int depth, int label, int depth_all, int label_all) : used(used), depth(depth), label(label), depth_all(depth_all), label_all(label_all) {} void print() { printf("used = %d\n", used); printf("depth = %d\n", depth); printf("label = %d\n", label); printf("depth_all = %d\n", depth_all); printf("label_all = %d\n", label_all); } }; int main() { int n; scanf("%d", &n); std::vector>> g(n); heavy_light_decomposition hld(n); for(int i = 0; i < n - 1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a].push_back({b, c}); g[b].push_back({a, c}); hld.add_edge(a, b); } hld.build(); std::vector dist(n), depth(n); auto dfs = [&](auto && dfs, int v, int par) -> void { for(auto e: g[v]) { if(e.first == par) continue; dist[e.first] = dist[v] + e.second; depth[e.first] = depth[v] + 1; dfs(dfs, e.first, v); } }; dfs(dfs, 0, -1); auto calc = [dist, &hld](int u, int v) { return dist[u] + dist[v] - 2LL * dist[hld.lca(u, v)]; }; auto f = [](node a, node b) { node ret; ret.used = 0; if(a.depth_all > b.depth_all) { ret.label_all = a.label_all; ret.depth_all = a.depth_all; } else { ret.label_all = b.label_all; ret.depth_all = b.depth_all; } if(a.used and b.used) { ret.used = 1; ret.label = ret.label_all; ret.depth = ret.depth_all; return ret; } else if(a.used and !b.used) { if(a.depth_all > b.depth) { ret.label = a.label_all; ret.depth = a.depth_all; } else { ret.label = b.label; ret.depth = b.depth; } } else if(!a.used and b.used) { if(a.depth > b.depth_all) { ret.label = a.label; ret.depth = a.depth; } else { ret.label = b.label_all; ret.depth = b.depth_all; } } else { if(a.depth > b.depth) { ret.label = a.label; ret.depth = a.depth; } else { ret.label = b.label; ret.depth = b.depth; } } return ret; }; auto gg = [](node a, int b) { if(b) { a.used = 1; a.depth = a.depth_all; a.label = a.label_all; } else { a.used = 0; a.depth = -1; a.label = -1; } return a; }; auto h = [](int a, int b) { return b; }; SegmentTree A(f, gg, h, node(), -1); A.init(n); for(int i = 0; i < n; i++) { int v = hld.inv[i]; A.set_val(i, node(0, -1, -1, depth[v], v)); } auto kiri = [&A](int l, int r) { A.update(l, r + 1, 1); }; auto irik = [&A](int l, int r) { A.update(l, r + 1, 0); }; int q; scanf("%d", &q); while(q--) { int k = 3; // scanf("%d", &k); std::vector> vec; for(int i = 0; i < k; i++) { int x; scanf("%d", &x); vec.push_back({depth[x], x}); } sort(begin(vec), end(vec)); if(k == 1) { printf("0\n"); continue; } i64 ans = calc(vec[0].second, vec[1].second); int c = hld.lca(vec[0].second, vec[1].second); hld.for_each(vec[0].second, vec[1].second, kiri); for(int i = 2; i < vec.size(); i++) { int v = vec[i].second; node tmp = node(); auto tanpo = [&](int l, int r) { tmp = f(tmp, A.query(l, r + 1)); }; hld.for_each(0, v, tanpo); if(tmp.depth == -1) { int u = hld.lca(v, c); ans += calc(u, v) + calc(u, c); hld.for_each(u, v, kiri); hld.for_each(u, c, kiri); c = hld.lca(u, v); } else { int u = tmp.label; ans += calc(u, v); hld.for_each(u, v, kiri); } } A.update(0, n, 0); printf("%lld\n", ans); } return 0; }