Submission #306753

#	Time	Username	Problem	Language	Result	Execution time	Memory
306753		MrDomino	Power Plant (JOI20_power)	C++14	0 / 100	4 ms	4992 KiB

power

#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 sol;

void dfs(int a, int p)
{
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dfs(b, a);
        }
    }
    dp[a] = -v[a];
    for (auto &b : g[a])
    {
        if (b != p)
        {
            dp[a] += dp[b];
        }
    }
    dp[a] = max(dp[a], v[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;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (v[i])
        {
            dfs(i, -1);
            sol = max(sol, dp[i]);
        }
    }
    cout << sol << "\n";
}

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