제출 #34654

#제출 시각아이디문제언어결과실행 시간메모리
34654nickyrio구슬과 끈 (APIO14_beads)C++14
0 / 100
6 ms4992 KiB
#include <bits/stdc++.h> #define FOR(i, a, b) for (int i = a; i<=b ; i++) #define FORD(i, a, b) for (int i = a; i>=b; i--) #define REP(i, a) for (int i = 0; i<a; i++) #define N 200100 #define pp pair<int, int> #define IO cin.tie(NULL);cout.tie(NULL); #define bit(S, i) ((S >> i) & 1) template<typename T> inline void read(T &x) { char c; bool neg = false; while (!isdigit(c = getchar()) && c != '-'); x = 0; if (c == '-') { neg = true; c = getchar(); } do { x = x * 10 + c - '0'; } while (isdigit(c = getchar())); if (neg) x = -x; } template<typename T> inline void write(T x) { if (x < 0) { putchar('-'); write(-x);return; } if (x < 10) { putchar(char(x + 48)); } else { write(x/10); putchar(char(48 + x%10)); } } template<typename T> inline void writeln(T x) { write(x); putchar('\n'); } using namespace std; int n; vector<pp> e[N]; long long dp[N][4]; void dfs(int u, int p) { REP(i, 4) dp[u][i] = -1e18; dp[u][0] = 0; for (pp tt : e[u]) if (tt.first != p) { int v = tt.first; int c = tt.second; dfs(v, u); //Prepare long long t0 = dp[v][0]; long long t1 = dp[v][1] + c; long long t2 = dp[v][2]; long long add = max(t0, max(t1, t2)); // FORD(i, 2, 0) { if (!i) { dp[u][3] += add; dp[u][3] = max(dp[u][3], dp[u][0] + max(t0, t2) + c); } dp[u][i] += add; if (i == 1) dp[u][i] = max(dp[u][i], dp[u][0] + t0 + c); if (i == 2) { dp[u][i] = max(dp[u][i], dp[u][1] + max(t0, t2) + c); dp[u][i] = max(dp[u][i], dp[u][3] + t0 + c); } } } dp[u][1] = max(dp[u][1], dp[u][3]); } int main() { IO; // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); int u, v, c; read(n); FOR(i, 2, n) { read(u);read(v);read(c); e[u].push_back(pp(v, c)); e[v].push_back(pp(u, c)); } dfs(1, -1); writeln(max(dp[1][0], dp[1][2])); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...