Submission #1255442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255442		damoon	Power Plant (JOI20_power)	C++20	100 / 100	164 ms	35572 KiB

power

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

const int L=2e5+10;
int n;
int a[L];
vector<int> adj[L];
int dp[L],pd[L];

void dfs(int v,int p){
    vector<int> ch;
    for(auto u:adj[v]){
        if(u != p){
            dfs(u,v);
            ch.pb(u);
        }
    }

    int V=0;
    for(auto u:ch){
        V += pd[u];
    }
    pd[v] = max(V-a[v], a[v]);
    dp[v] = V-a[v];

    V = 0;
    for(auto u:ch){
        V = max(V,pd[u]);
    }
    dp[v] = max(dp[v],V+a[v]);

    V = 0;
    for(auto u:ch){
        V = max(V,dp[u]);
    }
    dp[v] = max(dp[v],V);
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int i=1;i<=n;i++){
        char inp;
        cin>>inp;
        a[i] = (inp == '1');
    }

    dfs(1,0);
    cout<<dp[1]<<endl;
}

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