제출 #344762

#제출 시각아이디문제언어결과실행 시간메모리
344762Sara구슬과 끈 (APIO14_beads)C++14
0 / 100
4 ms5100 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define ll long long int #define F first #define S second #define pb push_back #define v00 dp[0][0][v] #define v01 dp[0][1][v] #define v10 dp[1][0][v] #define v11 dp[1][1][v] #define u00 dp[0][0][u] #define u01 dp[0][1][u] #define u10 dp[1][0][u] #define u11 dp[1][1][u] const ll M = 5; const ll N = 2e5 + 5; const ll LOG = 20; const int MOD = 1e9 + 7; const ll INF = 1e9 + 5; int n, dp[M][M][N]; vector < pair <int, int> > adj[N]; // dp[0][0][v] : (in sub[v] down : 0) && (v up_dn : 0) -> ok : v is emp // dp[0][1][v] : (in sub[v] down : 0) && (v up_dn : 1) -> ok : v is up_dn // dp[1][0][v] : (in sub[v] down : 1) && (v up_dn : 0) -> ok : v is dn || v is emp // dp[1][1][v] : (in sub[v] down : 1) && (v up_dn : 1) -> ok : v is up_dn void dfs(int v = 1, int p = 0, int up = -INF){ v00 = v01 = v10 = v11 = 0; int hlp[] = {0, -INF, -INF, -INF}; for (auto i : adj[v]){ int u = i.F, dn = i.S; if (u == p) continue; dfs(u, v, i.S); v11 = max({v11 + max(u00, u01), v01 + max(u10, u11), v10 + up + dn + u00, v00 + up + dn + u10}); v10 = max({v10 + max(u00, u01), v00 + max(u10, u11)}); v01 = max(v01 + max(u00, u01), v00 + up + dn + u00); v00 = v00 + max(u00, u01); hlp[3] = max({hlp[3] + max(u00, u01), hlp[2] + dn + u00, hlp[1] + dn + max(u00, u10)}); hlp[2] = max(hlp[2] + max(u00, u01), hlp[0] + dn + max(u00, u10)); hlp[1] = max(hlp[1] + max(u00, u01), hlp[0] + dn + u00); hlp[0] = hlp[0] + max(u00, u01); } v10 = max(v10, hlp[3]); return; } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n; for (int i = 0; i < n - 1; i ++){ int u, v, w; cin >> u >> v >> w; adj[u].pb({v, w}); adj[v].pb({u, w}); } dfs(); cout << max(dp[0][0][1], dp[1][0][1]) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...