Submission #651543

#	Time	Username	Problem	Language	Result	Execution time	Memory
651543		czhang2718	Power Plant (JOI20_power)	C++17	100 / 100	154 ms	35992 KiB

power

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i=a; i<=b; i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define f first
#define s second
#define nl '\n'
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef pair<int, int> pii;
#define nl '\n'

const int N=5e5;
int n;
vi adj[N];
string on;
int dp[N];
int ans=-1e9;

void dfs(int x, int par){
    int mx=0;
    for(int k:adj[x]){
        if(k==par) continue;
        dfs(k, x);
        mx=max(mx, dp[k]);
        dp[x]+=max(0, dp[k]);
    }
    if(on[x]=='1') ans=max(ans, mx+1);
    ans=max(ans, dp[x]-(on[x]=='1'));
    dp[x]=max(dp[x]-(on[x]=='1'), int(on[x]=='1'?1:-1e9));
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    rep(i,1,n-1){
        int u,v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    cin >> on;
    on='0'+on;

    dfs(1, 0);
    cout << ans;
}

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