Submission #1319038

#TimeUsernameProblemLanguageResultExecution timeMemory
1319038wangzhiyi33Power Plant (JOI20_power)C++20
100 / 100
151 ms28120 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#pragma GCC optimize("O3,unroll-loops")
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=2e5;

vector<int>adj[maxn+2];
int n,dp[maxn+2];
int ans;
int p[maxn+2];

void dfs(int cur,int par){
    int tot=0,mx=0;
    for(auto x : adj[cur]){
        if(x==par)continue;
        dfs(x,cur);
        tot+=dp[x],mx=max(mx,dp[x]);
    }
    
    ans=max({ans,mx+p[cur],tot-p[cur]});
    dp[cur]=max({p[cur],tot-p[cur]});

}

signed main(){
    cin>>n;
    for(int q=1;q<n;q++){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    for(int q=1;q<=n;q++){
        char x;
        cin>>x;
        p[q]=x-'0';
    }

    dfs(1,0);
    cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...