Submission #362091

#	Time	Username	Problem	Language	Result	Execution time	Memory
362091		doowey	Power Plant (JOI20_power)	C++14	100 / 100	215 ms	35012 KiB

power

#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 100;
vector<int> T[N];
int bt[N];
int sol = 1;
int dp[N];

void dfs(int u, int pp){
    vector<int> nx;
    for(auto x : T[u]){
        if(x==pp) continue;
        dfs(x,u);
        nx.push_back(x);
    }
    if(bt[u]){
        dp[u]=1;
    }
    for(auto q : nx){
        sol = max(sol, dp[q]+bt[u]);
    }
    int cum = 0;
    for(auto q : nx){
        cum += dp[q];
    }
    dp[u] = max(dp[u],cum-bt[u]);
    sol = max(sol, cum - bt[u]);
    for(auto q : nx){
        dp[u]=max(dp[u],dp[q]-bt[u]);
    }
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int u, v;
    for(int i = 1; i < n; i ++ ){
        cin >> u >> v;
        T[u].push_back(v);
        T[v].push_back(u);
    }
    char f;
    for(int i = 1; i <= n; i ++ ){
        cin >> f;
        bt[i]=f-'0';
    }
    dfs(1,-1);
    cout << sol << "\n";
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 53 / 53