제출 #1149978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149978		12345678	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	4936 KiB

beads

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, u, v, w, dp1[nx], dp2[nx];
vector<pair<int, int>> d[nx];

void dfs(int u, int p, int pw)
{
    int sm=0;
    vector<pair<int, int>> c;
    for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w), dp1[u]+=dp2[v], sm+=dp2[v], c.push_back({v, w});
    for (int i=0; i<c.size(); i++) 
    {
        for (int j=i+1; j<c.size(); j++) 
        {
            dp1[u]=max(dp1[u], sm-dp2[c[i].first]-dp2[c[j].first]+dp1[c[i].first]+dp1[c[j].first]+c[i].second+c[j].second);
        }
    }
    for (int i=0; i<c.size(); i++) dp2[u]=max(dp2[u], sm-dp2[c[i].first]+dp1[c[i].first]+c[i].second+pw);
    dp2[u]=max(dp2[u], dp1[u]);
    if (u==1&&0)
    {
        cout<<"debug ";
        for (auto x:c) cout<<x.first<<' ';
        cout<<'\n';
    }
    //cout<<"u "<<u<<' '<<dp1[u]<<' '<<dp2[u]<<'\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<<dp1[1];
}

/*
11 34
35 95
0 0
*/

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