Submission #306764

#TimeUsernameProblemLanguageResultExecution timeMemory
306764MrDominoPower Plant (JOI20_power)C++14
100 / 100
308 ms29752 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = (int) 2e5 + 7;
int n;
vector<int> g[N];
int v[N];
int dp[N];
int sum[N];
int sol;

void dfs(int a, int p)
{
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dfs(b, a);
        }
    }
    sum[a] = 0;
    for (auto &b : g[a])
    {
        if (b != p)
        {
            sum[a] += dp[b];
        }
    }
    dp[a] = max(sum[a] - v[a], v[a]);
}

void reroot(int a, int p)
{
    sum[a] -= dp[p];
    dp[a] = max(sum[a] - v[a], v[a]);
    sum[p] += dp[a];
    dp[p] = max(sum[p] - v[p], v[p]);
}

void dfs_solve(int a, int p)
{
    sol = max(sol, dp[a]);
    for (auto &b : g[a])
    {
        if (b != p)
        {
            reroot(a, b);
            dfs_solve(b, a);
            reroot(b, a);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    string s;
    cin >> s;
    for (int i = 1; i <= n; i++)
    {
        if (s[i - 1] == '1')
        {
            v[i] = 1;
            sol++;
        }
    }
    sol = min(sol, 2);
    dfs(1, -1);
    dfs_solve(1, -1);
    cout << sol << "\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...