Submission #528247

#TimeUsernameProblemLanguageResultExecution timeMemory
528247ajpianoPower Plant (JOI20_power)C++17
100 / 100
156 ms31308 KiB
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<int,int> pi;

const int large = 2e5+5;

int n, ans = 0;
vector<bool> power;
vector<int> edges[large];

vector<int> dp;

void dfs(int node, int par){
    int cans = 0;
    if(power[node]) cans = 1;
    int best = 0;
    int csum = 0;
    for(auto &a: edges[node]){
        if(a == par) continue;
        dfs(a,node);
        csum += dp[a];
        best = max(best,dp[a]);
    }
    if(power[node]){
        ans = max(ans,best+1);
        csum--;
    }
    cans = max(cans,csum);
    ans = max(ans,cans);
    dp[node] = cans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    dp.resize(n+1); power.resize(n+1);
    for(int i = 0; i < n-1; i++){
        int u,v; cin >> u >> v;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    for(int i = 1; i <= n; i++){
        char a; cin >> a;
        if(a == '1') power[i] = 1;
    }
    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...