Submission #1337865

#TimeUsernameProblemLanguageResultExecution timeMemory
1337865iamhereforfunPower Plant (JOI20_power)C++20
100 / 100
140 ms29012 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 3e5 + 5;
const int K = 1e2 + 5;
const int LG = 20;
const int INF = 1e9 + 5;
const int B = 1000;
const int MOD = 1e9 + 7;

int n, dp[N], ans;
string s;
vector<int> adj[N];

void dfs(int c, int p)
{
int mx = 0;
    for (int i : adj[c])
    {
        if (i == p)
            continue;
        dfs(i, c);
        if (s[c] == '1')
            ans = max(ans, dp[i] + 1);
        mx += dp[i];
    }
    if (s[c] == '1')
    {
        dp[c] = 1;
        mx--;
    }
    dp[c] = max(mx, dp[c]);
    ans = max(ans, dp[c]);
    // cout << dp[c] << " " << ans << " " << c << "\n";
}

inline void solve()
{
    cin >> n;
    ans = 0;
    for (int x = 0; x < n - 1; x++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    cin >> s;
    s = '0' + s;
    // for (int x = 1; x <= n; x++)
    // {
    //     if (s[x] == '1')
    //         cout << x << " ";
    // }
    // cout << "\n";
    dfs(1, 0);
    cout << ans << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...