Submission #1351187

#TimeUsernameProblemLanguageResultExecution timeMemory
1351187piolkPower Plant (JOI20_power)C++20
100 / 100
62 ms26148 KiB
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn=2e5 + 5;
vector<int> t[maxn];
int dp[maxn];
int ans=0;

string s;

void dfs(int v,int p){
    int mx=0;
    for (int u:t[v]){
        if (u==p) continue;
        dfs(u,v);
        dp[v]+=dp[u];
        mx=max(mx,dp[u]);
    }
    if (s[v-1]=='1'){
        if (dp[v]==0) dp[v]=1;
        else if (dp[v]>1) dp[v]--;
        ans=max(ans,mx+1);
    }
    ans=max(ans,dp[v]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin>>n;

    for (int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        t[a].push_back(b);
        t[b].push_back(a);
    }

    cin>>s;

    dfs(1,0);
    cout<<ans<<"\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...