#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 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'; } } } //===================================================================================================================================== int main(){ cin.tie(0)->sync_with_stdio(0); // fre(); cin >> n; for(int i = 1; i < n; i++){ cin >> u >> v >> w; u++; v++; adj[u].pb({v, w}); adj[v].pb({u, 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; } return 0; }

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