Submission #752019

#	Time	Username	Problem	Language	Result	Execution time	Memory
752019		vjudge1	Beads and wires (APIO14_beads)	C++17	100 / 100	193 ms	36656 KiB

beads

#include<bits/stdc++.h>
#define N 200100
#define int long long
using namespace std;
int n,f[N], a3[N],dp[N][2],dp2[N][2], a1[N],a2[N], bst[N],I=1e18;
vector<pair<int, int>> adj[N];
void dfs(int x){
	dp[x][0]=0;
	int m1=I,m2=I+1;
	for(auto [i,j]:adj[x])
        if(f[x]!=i){
            a3[i]=j;
            f[i]=x,dfs(i);
            int m=max(dp[i][1]+j,dp[i][0]);
            dp[x][0]+=m,m-=(dp[i][0]+j);
            if(m<m1)
                m2=m1,m1=m,bst[x]=i;
            else if(m<m2)
                m2=m;
        }
	a1[x]=m1,a2[x]=m2,dp[x][1]=dp[x][0]-a1[x];
}
void dfs2(int x){
	for(auto [i, j]:adj[x])
        if(i!=f[x]){
            dp2[i][0]=dp[x][0]-max(dp[i][1]+j,dp[i][0]);
            if(x>1)dp2[i][0]+=max(dp2[x][1]+a3[x],dp2[x][0]);
            int M=((bst[x]==i)?a2[x]:a1[x]);
            if(x>1)M=min(M,max(dp2[x][1]+a3[x],dp2[x][0])-(dp2[x][0]+a3[x]));
            dp2[i][1]=dp2[i][0]-M;
            dfs2(i);
        }
}
signed main(){
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n;
	for(int i=1;i<n;i++){
        int a, b, c;
		cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
	}
	dfs(1);
	dfs2(1);
	int ans=-I;
	for(int i=1;i<=n;i++){
		int temp=dp[i][0];
		if(i > 1)
            temp+=max(dp2[i][0],dp2[i][1]+a3[i]);
		ans=max(ans,temp);
	}
	cout << ans << '\n';
} 

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