Submission #755682

#TimeUsernameProblemLanguageResultExecution timeMemory
755682Desh03Election Campaign (JOI15_election_campaign)C++17
10 / 100
144 ms33248 KiB
#include <bits/stdc++.h> using namespace std; vector<int> dep, dp, dp2; vector<vector<int>> g, up; vector<vector<tuple<int, int, int>>> qr; int t, lg; void dfs(int u, int p) { up[0][u] = p; for (int i = 1; i < lg; i++) up[i][u] = up[i - 1][up[i - 1][u]]; for (int v : g[u]) if (v ^ p) dep[v] = dep[u] + 1, dfs(v, u); } int getkth(int u, int k) { for (int i = 0; i < lg; i++) if (k >> i & 1) u = up[i][u]; return u; } void calc_dp(int u, int p) { for (int v : g[u]) if (v ^ p) { calc_dp(v, u); dp2[u] += dp[v]; } dp[u] = dp2[u]; for (auto [x, y, w] : qr[u]) { int c1 = getkth(x, dep[x] - dep[u] - 1); int c2 = getkth(y, dep[y] - dep[u] - 1); int cost = w + dp2[x] + dp2[y] + dp2[u]; if (x ^ u) cost -= dp[c1]; else cost -= dp2[u]; if (y ^ u) cost -= dp[c2]; else cost -= dp2[u]; dp[u] = max(dp[u], cost); } } int lca(int u, int v) { if (dep[u] < dep[v]) swap(u, v); int k = dep[u] - dep[v]; for (int i = 0; i < lg; i++) if (k >> i & 1) u = up[i][u]; if (u == v) return u; for (int i = lg - 1; i >= 0; i--) if (up[i][u] ^ up[i][v]) u = up[i][u], v = up[i][v]; return up[0][u]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n; cin >> n; while ((1 << lg) <= n) ++lg; g.resize(n), up = vector<vector<int>> (lg, vector<int> (n)), dp.resize(n), dp2.resize(n), dep.resize(n), qr.resize(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; --u, --v; g[u].push_back(v); g[v].push_back(u); } dfs(0, 0); int q; cin >> q; while (q--) { int u, v, w; cin >> u >> v >> w; --u, --v; qr[lca(u, v)].push_back({u, v, w}); } calc_dp(0, 0); cout << dp[0] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...