Submission #1033488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033488		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	97 ms	32848 KiB

power

#include<bits/stdc++.h>
using namespace std;
int dp[200100][2],hasgen[200100];
vector<int>adj[200100];
void dfs(int n,int p){
    int A=-hasgen[n],B=0,C=0;
    for(auto i:adj[n]){
        if(i==p)continue;
        dfs(i,n);
        A+=dp[i][1];
        B=max(B,dp[i][0]);
        C=max(C,dp[i][1]);
    }
    dp[n][0]=max({hasgen[n]+C,A,B});
    dp[n][1]=max(hasgen[n],A);
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>>n;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for(int i=1;i<=n;i++){
        char c;
        cin>>c;
        hasgen[i]=c-48;
    }
    dfs(1,0);
    cout<<dp[1][0];
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53