#include<bits/stdc++.h> using namespace std; //===================================================================================================================================== #define ll long long #define ld long double #define fi first #define se second #define pb push_back #define pll pair<ll, ll> #define pli pair<ll, int> #define pil pair<int, ll> #define pii pair<int, int> #define BIT(i, mask) ((mask >> (i)) & 1) #define DAOBIT(i, mask) ((mask ^ (1 << i))) #define OFFBIT(i, mask) ((mask & ~(1 << (i)))) #define ONBIT(i, mask) ((mask | (1 << (i)))) #define all(x) (x).begin(), (x).end() #define Unique(v) v.erase(unique(all(v)), v.end()); #define nmax 1000007 //===================================================================================================================================== const int N = 1e6 + 7; const ll mod = 1e9 + 6; const ll MOD = 1e9 + 7; const ll inf = 1e18; bool check_sub2 = 1; int n, q; vector<pil> adj[N]; int ts[10]; int u, v; ll w; ll sum_w; //===================================================================================================================================== void fre(){ freopen("TET.INP", "r", stdin); freopen("TET.out", "w", stdout); } ll gcd(ll a, ll b){ return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b){ return (a / gcd(a, b)) * b; } namespace sub2{ ll d[N]; void pre_sub2(int u, int p, ll w){ d[u] = w; for(pil e : adj[u]){ int v = e.fi; ll w2 = e.se; if(v == p) continue; pre_sub2(v, u, w + w2); } } void solve(){ int root = 0; for(int i = 1; i <= n; i++) if(adj[i].size() == 1) root = i; pre_sub2(root, 0, 0); while(q--){ for(int i = 1; i <= 5; i++) cin >> ts[i]; for(int i = 1; i <= 5; i++) ts[i]++; ll ans = 0; for(int i = 1; i <= 5; i++){ for(int j = 1; j <= 5; j++){ ans = max(ans, d[ts[j]] - d[ts[i]]); // cout << ts[j] << ' ' << ts[i] << ' ' << d[ts[j]] - d[ts[i]] << '\n'; } } cout << ans << '\n'; } } } namespace sub3{ int cnt[N]; ll wtp[N]; bool f[N]; void dfs_sub3(int u, int p){ if(f[u]) cnt[u]++; for(pil e : adj[u]){ int v = e.fi; ll w2 = e.se; if(v == p) continue; dfs_sub3(v, u); wtp[v] = w2; cnt[u] += cnt[v]; } } void solve(){ while(q--){ for(int i = 1; i <= 5; i++) cin >> ts[i]; for(int i = 1; i <= 5; i++) ts[i]++; for(int i = 1; i <= 5; i++) f[ts[i]] = 1; ll ans = sum_w; dfs_sub3(1, 0); for(int i = 1; i <= n; i++){ if(cnt[i] == 0 || cnt[i] == 5) ans -= wtp[i]; cnt[i] = 0; } for(int i = 1; i <= 5; i++) f[ts[i]] = 0; cout << ans << '\n'; } } } struct LCA { int n, root, LG; vector<int> h; vector<vector<int>> up; vector<vector<ll>> me; vector<vector<ll>> sum; vector<vector<pll>> 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 main(){ cin.tie(0)->sync_with_stdio(0); // fre(); cin >> n; LCA t(n); for(int i = 1; i < n; i++){ cin >> u >> v >> w; u++; v++; adj[u].pb({v, w}); adj[v].pb({u, w}); t.add_edge(u, v, w); sum_w += w; check_sub2 &= (adj[u].size() <= 2); check_sub2 &= (adj[v].size() <= 2); } if(n == 5 && q == 1){ cout << sum_w << '\n'; return 0; } cin >> q; if(check_sub2){ sub2 :: solve(); return 0; } if(n <= 50000 && q <= 100){ sub3 :: solve(); return 0; } t.dfs(1); while(q--){ vector<int> nodes(5); for(int i = 0; i < 5; i++){ cin >> nodes[i]; nodes[i]++; } sort(nodes.begin(), nodes.end(), [&](int u, int v){ return t.tin[u] < t.tin[v]; }); vector<int> vt = nodes; for(int i = 0; i + 1 < nodes.size(); i++){ int w = t.get_lca(nodes[i], nodes[i + 1]); vt.pb(w); } sort(vt.begin(), vt.end(), [&](int u, int v){ return t.tin[u] < t.tin[v]; }); Unique(vt); ll ans = 0; vector<int> st; for(int vtx : vt){ while(!st.empty() && !t.is_ancestor(st.back(), vtx)) st.pop_back(); if(!st.empty()){ ans += t.path_sum(st.back(), vtx); } st.pb(vtx); } cout << ans << '\n'; } return 0; }

roadsideadverts.cpp: In function 'void fre()':
roadsideadverts.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen("TET.INP", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen("TET.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~