Submission #1332510

#TimeUsernameProblemLanguageResultExecution timeMemory
1332510WarinchaiPower Plant (JOI20_power)C++20
100 / 100
133 ms29764 KiB
#include<bits/stdc++.h>
using namespace std;

vector<int>adj[200005];
int ar[200005];
int dp[200005];
int ans=0;

void dfs(int u,int p){
    int sum=0;
    int mx=0;
    for(auto x:adj[u])if(x!=p){
        dfs(x,u);
        sum+=dp[x];
        mx=max(mx,dp[x]);
    }
    dp[u]=max(ar[u],sum-ar[u]);
    ans=max({ans,dp[u],mx+ar[u]});
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(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);
    }
    string s;cin>>s;
    for(int i=1;i<=n;i++){
        ar[i]=s[i-1]-'0';
    }
    dfs(1,0);
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...