Submission #1325020

#TimeUsernameProblemLanguageResultExecution timeMemory
1325020NValchanovBeads and wires (APIO14_beads)C++20
28 / 100
1093 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);

        int curmax = dp[v][0];

        if(curmax < dp[v][1])
            curmax = dp[v][1];

        dp[u][0] += curmax;
    }

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

        if(v == par)
            continue;

        int curmax = dp[v][0];

        if(curmax < dp[v][1])
            curmax = dp[v][1];

        int cur = dp[u][0] - curmax + dp[v][0] + cost + up[u];

        if(cur > dp[u][1])
            dp[u][1] = cur;
    }
}

void solve()
{
    int ans = 0;

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

        if(ans < dp[i][0])
            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...