/*Code by TMQ - Completed*/ #include <bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define ld long double #define ii pair<ll, ll> #define fi first #define se second #define pb push_back #define em emplace #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++) #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++) #define FIV(i, a, b) for (int i = (a), _b = (b); i >= _b; i--) #define all(x) (x).begin(), (x).end() #define reset(a, x) (memset(a, x, sizeof(a))); #define Unique(v) v.erase(unique(all(v)), v.end()); #define testcase \ int tc; \ cin >> tc; \ while (tc--) \ solve(); #define howlong cerr << "Time elapsed: " << fixed << setprecision(9) << (double)clock() / CLOCKS_PER_SEC << "s"; #define what_is(x) cerr << #x << " is " << x << '\n'; ll inline GCD(ll a, ll b) { return !b ? abs(a) : GCD(b, a % b); } ll inline LCM(ll a, ll b) { return (a / GCD(a, b) * b); } template <class X, class Y> bool maximize(X &x, Y y) { if (x < y) { x = y; return true; } return false; }; template <class X, class Y> bool minimize(X &x, Y y) { if (x > y) { x = y; return true; } return false; }; ///=====================================s======================================== #define BIT(i, mask) ((mask >> (i)) & 1) #define DAOBIT(i, mask) ((mask ^ (1 << i))) #define OFFBIT(i, mask) ((mask & ~(1 << (i)))) // ONBIT macro was broken in original; not used here ///============================================================================ void __print(int x) { cerr << x; } void __print(long x) { cerr << x; } void __print(long long x) { cerr << x; } void __print(unsigned x) { cerr << x; } void __print(unsigned long x) { cerr << x; } void __print(unsigned long long x) { cerr << x; } void __print(float x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "true" : "false"); } template <typename T, typename V> void __print(const pair<T, V> &x) { cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}'; } template <typename T> void __print(const T &x) { int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}"; } void _print() { cerr << "]\n"; } template <typename T, typename... V> void _print(T t, V... v) { __print(t); if (sizeof...(v)) cerr << ", "; _print(v...); } #ifndef ONLINE_JUDGE #define debug(x...) \ { \ cerr << "[" << #x << "] = ["; \ _print(x); \ } #else #define debug(x...) #endif ///============================================================================ void TASK(string task) { if (fopen((task + ".inp").c_str(), "r")) { freopen((task + ".inp").c_str(), "r", stdin); freopen((task + ".out").c_str(), "w", stdout); } } ///============================================================================ const ll mod = 1e9 + 7; const ll inf = (ll)1e18 + 10; const ll nmax = 5e4 + 5; ///============================================================================ struct LCA { int n, root, LG; vector<int> h; vector<vector<int>> up; vector<vector<ll>> me; vector<vector<ll>> sum; vector<vector<ii>> adj; vector<int> tin, tout; int timer; LCA(int n, int r = 1) : n(n), root(r), adj(n + 1), h(n + 1) { LG = 1; while ((1 << LG) <= n) LG++; up.assign(n + 1, vector<int>(LG)); me.assign(n + 1, vector<ll>(LG, 0)); sum.assign(n + 1, vector<ll>(LG, 0)); tin.assign(n + 1, 0); tout.assign(n + 1, 0); timer = 0; } void add_edge(int u, int v, ll w = 1) { adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } void dfs(int u = -1, int p = -1) { if (u == -1) u = root; tin[u] = ++timer; up[u][0] = (p == -1 ? u : p); for (int j = 1; j < LG; ++j) { up[u][j] = up[up[u][j - 1]][j - 1]; me[u][j] = max(me[u][j - 1], me[up[u][j - 1]][j - 1]); sum[u][j] = sum[u][j - 1] + sum[up[u][j - 1]][j - 1]; } for (auto [v, w] : adj[u]) { if (v == p) continue; h[v] = h[u] + 1; me[v][0] = w; sum[v][0] = w; dfs(v, u); } tout[u] = ++timer; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; } int ancestor_k(int u, int k) { for (int j = 0; j < LG; ++j) if (k >> j & 1) u = up[u][j]; return u; } int get_lca(int u, int v) { if (h[u] < h[v]) swap(u, v); for (int j = LG - 1; j >= 0; --j) if (h[u] - (1 << j) >= h[v]) u = up[u][j]; if (u == v) return u; for (int j = LG - 1; j >= 0; --j) if (up[u][j] != up[v][j]) { u = up[u][j]; v = up[v][j]; } return up[u][0]; } ll path_sum(int u, int v) { ll res = 0; if (h[u] < h[v]) swap(u, v); for (int j = LG - 1; j >= 0; --j) if (h[u] - (1 << j) >= h[v]) { res += sum[u][j]; u = up[u][j]; } if (u == v) return res; for (int j = LG - 1; j >= 0; --j) if (up[u][j] != up[v][j]) { res += sum[u][j]; res += sum[v][j]; u = up[u][j]; v = up[v][j]; } res += sum[u][0]; res += sum[v][0]; return res; } int get_dist(int u, int v) { int l = get_lca(u, v); return h[u] + h[v] - h[l] * 2; } }; int n, q, a, b, c, d, e; ///============================================================================ int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); TASK("TET"); cin >> n; LCA l(n); for (int i = 1; i < n; i++) { int u, v; long long w; cin >> u >> v >> w; u++; v++; l.add_edge(u, v, w); } l.dfs(1, -1); cin >> q; while (q--) { vector<int> nodes(5); for (int i = 0; i < 5; ++i) { int x; cin >> x; x++; nodes[i] = x; } sort(nodes.begin(), nodes.end(), [&](int u, int v) { return l.tin[u] < l.tin[v]; }); vector<int> vt = nodes; for (int i = 0; i + 1 < nodes.size(); ++i) { int w = l.get_lca(nodes[i], nodes[i + 1]); vt.push_back(w); } sort(vt.begin(), vt.end(), [&](int u, int v) { return l.tin[u] < l.tin[v]; }); Unique(vt); // for (auto x : vt) // { // cout << x << ' '; // } // cout << '\n'; ll res = 0; vector<int> st; for (int vtx : vt) { while (!st.empty() && !l.is_ancestor(st.back(), vtx)) st.pop_back(); if (!st.empty()) { res += l.path_sum(st.back(), vtx); ///debug(st.back(), vtx, l.path_sum(st.back(), vtx)); } st.push_back(vtx); } cout << res << '\n'; } return 0; }

roadsideadverts.cpp: In function 'void TASK(std::string)':
roadsideadverts.cpp:108:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |                 freopen((task + ".inp").c_str(), "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:109:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |                 freopen((task + ".out").c_str(), "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~