제출 #984650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
984650		aaaaaarroz	Power Plant (JOI20_power)	C++17	100 / 100	196 ms	32696 KiB

power

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, x, y, answer = 0;
string power;
vector<ll> adj[200005];
ll dp[200005], ans[200005];
vector<ll> visited;
    
void dfs(ll from)
{
    visited[from] = true;
    ll summ = 0, maxx = 0;
    for (ll u: adj[from])
    {
        if (visited[u]) continue;
        dfs(u);
        summ+=dp[u];
        maxx = max(maxx, dp[u]);
    }
    if (power[from-1]=='1') {
        ans[from] = max(summ-1, maxx + 1); 
        dp[from] = max(1LL, summ-1);
    }
    else {
        ans[from] = dp[from] = summ;
    }
    answer = max(answer, ans[from]);
}
int main()
{
    cin>>n;
    for (ll i=0; i<n-1; ++i)
    {
        cin>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    cin >> power;
    visited.assign(n+1, false);
    dfs(1);
    cout<<answer<<"\n";
    return 0;
}

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