제출 #1339555

#제출 시각아이디문제언어결과실행 시간메모리
1339555hoangtien69Power Plant (JOI20_power)C++20
100 / 100
82 ms28832 KiB
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;

int n;
vector<int> adj[MAXN];
int cur = 0;
int dp[MAXN];
string s;
int ans = 0;

void dfs(int u, int par)
{
    int total = 0;
    int maxx = 0;
    for (int v : adj[u])
    {
        if (v == par)
        {
            continue;
        }
        dfs(v, u);
        total += dp[v];
        maxx = max(maxx, dp[v]);
    }
    if (s[u - 1] == '1')
    {
        ans = max({ans, total - 1, maxx + 1});
    }
    else
    {
        ans = max(ans, total);
    }
    int cur = 0;
    if (s[u - 1] == '1')
    {
        cur = 1;
    }
    dp[u] = max(cur, total - cur);
}

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

    cin >> n;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        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...