Submission #763250

#	Time	Username	Problem	Language	Result	Execution time	Memory
763250		vjudge1	Power Plant (JOI20_power)	C++17	100 / 100	185 ms	28424 KiB

power

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn = 2e5 + 5;

vector<ll> adj[maxn];
string s;
ll ans = 1;
ll dp[maxn];
void dfs(ll src, ll parent)
{
    ll maxt = -1;
    for (auto sex: adj[src])
    {
        if (sex != parent)
        {
            dfs(sex, src);
            dp[src] += dp[sex];
            maxt = max(maxt, dp[sex]);
        }
    }
    ll gay = s[src - 1] - '0';
    dp[src] = max(gay,  dp[src] - gay);
    ans = max({ans, maxt + gay, dp[src]});
}

int main()
{
    ll n;
    cin >> n;
    ll u, v;
    for (ll i = 1; i <= n - 1; ++i)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cin >> s;
    dfs(1, 0);
    cout << ans;
    
}

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