Submission #1165877

#TimeUsernameProblemLanguageResultExecution timeMemory
1165877AlgorithmWarriorPower Plant (JOI20_power)C++20
100 / 100
182 ms29268 KiB
#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int n;
vector<int>tree[MAX];
int special[MAX];
int ans;
int dp[MAX];

void read(){
    cin>>n;
    int i;
    for(i=1;i<n;++i){
        int u,v;
        cin>>u>>v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    for(i=1;i<=n;++i){
        char ch;
        cin>>ch;
        special[i]=ch-'0';
    }
}

void maxself(int& x,int val){
    if(x<val)
        x=val;
}

void dfs(int nod,int tata){
    int sum=0,mxm=0;
    for(auto fiu : tree[nod])
        if(fiu!=tata){
            dfs(fiu,nod);
            sum+=dp[fiu];
            maxself(mxm,dp[fiu]);
        }
    if(special[nod]){
        maxself(ans,1+mxm);
        dp[nod]=max(sum-1,1);
    }
    else
        dp[nod]=sum;
    maxself(ans,dp[nod]);
}

int main()
{
    read();
    dfs(1,0);
    cout<<ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...