Submission #1325016

#TimeUsernameProblemLanguageResultExecution timeMemory
1325016NValchanovBeads and wires (APIO14_beads)C++20
28 / 100
1096 ms1080 KiB
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 2e5 + 10;

struct Edge
{
    int to, cost;

    Edge(){};

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

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

void read()
{
    cin >> n;

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

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

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

        if(v == par)
            continue;

        dfs(v, u);

        up[v] = cost;
    }
}

void dfs2(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;

        dfs2(v, u);

        dp[u][0] += 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] = max(dp[u][1], dp[u][0] - 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);

        dfs2(i, i);

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

    cout << ans << endl;
}

int main()
{
    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...