제출 #1325019

#제출 시각아이디문제언어결과실행 시간메모리
1325019NValchanov구슬과 끈 (APIO14_beads)C++20
28 / 100
1095 ms1080 KiB
#include <iostream>
#include <vector>

const int MAXN = 2e5 + 10;

struct Edge
{
    int to, cost;

    Edge(){};

    Edge(int to, int cost)
    {
        this->to = to;
        this->cost = cost;
    }
};

int n;
std::vector < Edge > adj[MAXN];
int dp[MAXN][2];
int up[MAXN];

void read()
{
    std::cin >> n;

    for(int i = 1; i < n; i++)
    {
        int u, v, cost;
        std::cin >> u >> v >> cost;

        adj[u].push_back(Edge(v, cost));
        adj[v].push_back(Edge(u, cost));
    }
}

void dfs(int u, int par)
{
    dp[u][0] = dp[u][1] = 0;

    for(Edge &e : adj[u])
    {
        int v = e.to;
        int cost = e.cost;

        if(v == par)
            continue;

        up[v] = cost;

        dfs(v, u);

        dp[u][0] += std::max(dp[v][0], dp[v][1]);
    }

    for(Edge &e : adj[u])
    {
        int v = e.to;
        int cost = e.cost;

        if(v == par)
            continue;

        dp[u][1] = std::max(dp[u][1], dp[u][0] - std::max(dp[v][0], dp[v][1]) + dp[v][0] + cost + up[u]);
    }
}

void solve()
{
    int ans = 0;

    for(int i = 1; i <= n; i++)
    {
        dfs(i, i);

        ans = std::max(ans, dp[i][0]);
    }

    std::cout << ans << '\n';
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    read();
    solve();

    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...