제출 #198230

#제출 시각아이디문제언어결과실행 시간메모리
198230parsa_mobed구슬과 끈 (APIO14_beads)C++14
28 / 100
1070 ms3192 KiB
#include <bits/stdc++.h>

using namespace std;
#define pii pair <int , int>
#define F first
#define S second
const int N = 1e5 + 10, inf = 1e9 + 5;
int dp[N][2];
vector <pii> g[N];

void dfs(int v, int p = 0)
{
    int sum = 0;
    for (pii u : g[v]) if (u.F != p) {
        dfs(u.F, v);
        sum += max(dp[u.F][1] + u.S, dp[u.F][0]);
    }
    dp[v][0] = sum;
    for (pii u : g[v]) if (u.F != p)
        dp[v][1] = max(dp[v][1], sum - max(dp[u.F][1] + u.S, dp[u.F][0]) + dp[u.F][0] + u.S);
}

int main()
{
    int n; cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = -inf;
        dfs(i);
        ans = max(ans, dp[i][0]);
    }
    cout << ans << "\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...