제출 #763653

#제출 시각아이디문제언어결과실행 시간메모리
763653vjudge1Power Plant (JOI20_power)C++17
100 / 100
140 ms26860 KiB
#include <bits/stdc++.h>

using namespace std;

int n;
vector<vector<int>> adjList;
vector<int> parent;
string isBased;

vector<int> dp;

int result = 0;

void depthFirstSearch(int u, int p)
{
    int V = 0;
    for (auto &v : adjList[u])
        if (v != p)
        {
            depthFirstSearch(v, u);
            dp[u] += dp[v];
            if (dp[v] > dp[V])
                V = v;
        }

    if (isBased[u] == '1')
    {
        result = max(dp[V] + 1, result);
        dp[u] = max(1, dp[u] - 1);
    }

    result = max(dp[u], result);
}

int main()
{
    // freopen("inp.txt", "r", stdin);

    ios::sync_with_stdio(false);

    cin >> n;
    adjList.resize(n + 1);
    parent.resize(n + 1);
    for (int u, v, i = 1; i < n; i++)
    {
        cin >> u >> v;
        adjList[u].emplace_back(v);
        adjList[v].emplace_back(u);
    }
    cin >> isBased;
    isBased = "!" + isBased;

    dp.resize(n + 1);
    depthFirstSearch(1, -1);

    cout << result;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...