Submission #1176472

#TimeUsernameProblemLanguageResultExecution timeMemory
117647212345678Beads and wires (APIO14_beads)C++17
0 / 100
2 ms4936 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, u, v, w, dp[nx][2][2];
vector<pair<int, int>> d[nx];

void dfs(int u, int p, int pw)
{
    int sm=0;
    for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w), sm+=max(dp[v][0][1], dp[v][1][1]);
    for (int i=0; i<d[u].size(); i++)
    {
        for (int j=i+1; j<d[u].size(); j++)
        {
            auto [x, xw]=d[u][i];
            auto [y, yw]=d[u][j];
            if (x==p||y==p) continue;
            dp[u][0][0]=max(dp[u][0][0], sm-max(dp[x][0][1], dp[x][1][1])+max({dp[x][0][0], dp[x][1][0], dp[x][1][1]})-max(dp[y][0][1], dp[y][1][1])+max({dp[y][0][0], dp[y][1][0], dp[y][1][1]})+xw+yw);
        }
    }
    for (int i=0; i<d[u].size(); i++)
    {
        auto [x, xw]=d[u][i];
        if (x==p) continue;
        dp[u][0][1]=max(dp[u][0][1], sm-max(dp[x][0][1], dp[x][1][1])+max({dp[x][0][0], dp[x][1][0], dp[x][1][1]})+xw+pw);
        dp[u][1][0]+=max({dp[x][0][0], dp[x][0][1], dp[x][1][0], dp[x][1][1]});
        dp[u][1][1]+=max({dp[x][0][1], dp[x][1][1]});
    }
    //cout<<"dp "<<u<<' '<<dp[u][0][0]<<' '<<dp[u][0][1]<<' '<<dp[u][1][0]<<' '<<dp[u][1][1]<<'\n';
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    dfs(1, 1, 0);
    cout<<max({dp[1][0][0], dp[1][1][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...