Submission #1255442

#TimeUsernameProblemLanguageResultExecution timeMemory
1255442damoonPower Plant (JOI20_power)C++20
100 / 100
164 ms35572 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...