제출 #1146150

#제출 시각아이디문제언어결과실행 시간메모리
1146150fatman87878Power Plant (JOI20_power)C++20
100 / 100
127 ms28864 KiB
#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=2e5+5;

int n,dp[maxN],ans;

string s;

vector<int> adj[maxN];

void dfs(int now,int last){
    dp[now] = -(s[now]=='1');
    int mx = 0;
    for(int i:adj[now])if(i!=last){
        dfs(i,now);
        dp[now]+=dp[i];
        mx = max(mx,dp[i]);
    }
    dp[now] = max((int)(s[now]=='1'),dp[now]);
    ans = max({ans,dp[now],mx+(s[now]=='1')});
    return;
}

int main(){
    IOS
    cin>>n;
    for(int a,b,i = 1;i<n;i++)cin>>a>>b,adj[adj[a].emplace_back(b)].emplace_back(a);
    cin>>s;
    s=' '+s;
    dfs(1,1);
    cout<<ans<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...