Submission #1164416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164416		t9unkubj	Power Plant (JOI20_power)	C++20	100 / 100	64 ms	20096 KiB

power

#include"bits/stdc++.h"
using namespace std;
#ifndef EVAL
#define dbg(x) cout<<#x<<" := " <<x<<endl;
#define dbgv(x) \
for(int vv=0;vv<x.size();vv++){if(vv)cout<<"  ";\
    cout<<x[vv];\
}\
cout<<endl;\

#else
#define dbg(x) (void)x
#define dbgv(x) (void)x
#endif
using ll=long long;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define drep(i,n) for(ll i=ll(n)-1;i>=0;i--)
#define REP(i,n,m) for(ll i=(ll)(n);i<(ll)(m);i++)
#define DREP(i,n,m) for(ll i=(ll)(n);i>=(ll)(m);i--)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
template<class T,class F>
int chmin(T&a,F b){
    if(a>b){
        a=b;
        return 1;
    }
    return 0;
}
template<class T,class F>
int chmax(T&a,F b){
    if(a<b){
        a=b;
        return 1;
    }
    return 0;
}
void solve(){
    int n;
    cin>>n;
    vvc<int>g(n);
    rep(i,n-1){
        int a,b;
        cin>>a>>b;
        g[--a].push_back(--b);
        g[b].push_back(a);
    }
    string s;
    cin>>s;
    int ans=0;
    auto dfs=[&](auto&dfs,int u,int v)->int{
        ll sm=0;
        ll mx=0;
        for(auto&x:g[u]){
            if(x==v)continue;
            auto res=(dfs(dfs,x,u));
            sm+=res;
            chmax(mx,res);
        }
        if(s[u]=='1'){
            chmax(ans,mx+1);
            chmax(ans,sm-1);
            sm=max<int>(1,sm-1);
        }else{
            chmax(ans,sm);
        }
        return sm;
    };
    dfs(dfs,0,-1);
    cout<<ans<<"\n";
}
int main(){
#ifndef EVAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
    cin.tie(0)->sync_with_stdio(0);
    solve();
}
/*
2*on-シュタイナー木のsizeがうれしさ
dp[v]:=v を塗った時のmax


*/

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