제출 #763250

#제출 시각아이디문제언어결과실행 시간메모리
763250vjudge1Power Plant (JOI20_power)C++17
100 / 100
185 ms28424 KiB
#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;
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...