Submission #316161

#	Time	Username	Problem	Language	Result	Execution time	Memory
316161		laoriu	Beads and wires (APIO14_beads)	C++14	0 / 100	4 ms	4992 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
using ll = long long ;
//#define int long long

using ii = pair < int , int > ;
const int MAX = 2e5+4,mod=1e9+7;
const int inf=0x3f3f3f3f;
int n,m;
vector < ii > pr[MAX];
void minn(int &a , int b){
if(b<a) a=b;
}
void maxx(int &a , int b){
if(b>a) a=b;
}
int dp[2][MAX];
void DFS(int v,int trc){
    int temp=0;
    for(ii u:pr[v])if(u.X!=trc){
        DFS(u.X,v);
        temp+=max(dp[1][u.X]+u.Y,dp[0][u.X]);
    }
    dp[1][v]=-inf;
    dp[0][v]=temp;
    for(ii u:pr[v])if(u.X!=trc){
        int x=dp[0][u.X]+u.Y- max(dp[1][u.X]+u.Y,dp[0][u.X]);
        maxx(dp[0][v],dp[1][v]+x+temp);
        maxx(dp[1][v],x );
    }
    dp[1][v]+=temp;
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("beads.inp", "r", stdin);//freopen("beads.out", "w", stdout);
    cin>>n;
    for(int i=1,x,y,c;i<n;i++){
        cin>>x>>y>>c;
        pr[x].pb(ii(y,c));
        pr[y].pb(ii(x,c));
    }
    DFS(1,0);
    cout<<dp[0][1];

}

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