제출 #752009

#제출 시각아이디문제언어결과실행 시간메모리
752009vjudge1구슬과 끈 (APIO14_beads)C++17
28 / 100
1070 ms5844 KiB
#include<bits/stdc++.h> using namespace std; long long dp[200100][2]; vector<pair<int, long long>> adj[200100]; void dfs(int n, int p) { dp[n][0] = 0; dp[n][1] = -1e18; long long m1=-1e18; for(auto [i, j]: adj[n]) { if(i!=p) { dfs(i, n); long long X = max(dp[i][1]+j, dp[i][0]); dp[n][0]+=X; long long x = dp[i][0] + j - X; m1 = max(m1, x); } } dp[n][1]=dp[n][0]+m1; } int main() { cin.sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for(int i = 1; i < n; i++) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } long long mx = 0; for(int i = 1; i <= n; i++) { dfs(i, 0); mx = max(mx, dp[i][0]); } cout << mx << '\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...