Submission #821764

#	Time	Username	Problem	Language	Result	Execution time	Memory
821764		vjudge1	Power Plant (JOI20_power)	C++14	100 / 100	109 ms	28748 KiB

power

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 2e5 ;
int n, s, ans, dp[N + 1] ;
char c[N + 1] ;
vector<int> v[N + 1] ;
void dfs(int city, int last)
{
    int sum = 0, mx = 0 ;
    for(int i : v[city])
    {
        if(i == last)
            continue ;
        dfs(i, city) ;
        sum += max(0, dp[i]) ;
        mx = max(mx, dp[i]) ;
    }
    dp[city] = max(c[city] - '0', sum - ((c[city] ^ 1) == '0')) ;
    if(c[city] == '1')
        ans = max(ans, mx + 1) ;
    ans = max(ans, dp[city]) ;
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n ;
    for(int i = 1 ; i < n ; i++)
    {
        int a, b ;
        cin >> a >> b ;
        v[a].push_back(b) ;
        v[b].push_back(a) ;
    }
    for(int i = 1 ; i <= n ; i++)
        cin >> c[i] ;
    dfs(1, 0) ;
    cout << ans ;
    return 0 ;
}

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