Submission #1176454

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176454		12345678	Beads and wires (APIO14_beads)	C++17	0 / 100	3 ms	4936 KiB

beads

#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])-max(dp[y][0][1], dp[y][1][1])+max(dp[y][0][0], dp[y][1][0])+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])+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], dp[1][1][1]});
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43