제출 #1281946

#제출 시각아이디문제언어결과실행 시간메모리
1281946SSKMFPower Plant (JOI20_power)C++20
100 / 100
123 ms18784 KiB
#include <bits/stdc++.h>
using namespace std;

vector <int> adiacenta[200001];
char tip[200001];
int rezultat;

inline int Parcurgere (const int nod , const int sursa)
{
    int candidat = (tip[nod - 1] == '1' ? -1 : 0) , maxim = 0;
    for (auto& vecin : adiacenta[nod]) {
        if (vecin != sursa)
        { 
            const int termen = Parcurgere(vecin , nod);
            maxim = max(maxim , termen);
            candidat += termen;
        }
    }

    if (tip[nod - 1] == '1')
        { rezultat = max(rezultat , maxim + 1); }
    
    rezultat = max(rezultat , candidat);
    return max(candidat , tip[nod - 1] == '1' ? 1 : 0);
}

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int numar_noduri;
    cin >> numar_noduri;

    for (int indice = 1 ; indice < numar_noduri ; indice++)
    {
        int nod[2]; cin >> nod[0] >> nod[1];
        adiacenta[nod[0]].push_back(nod[1]);
        adiacenta[nod[1]].push_back(nod[0]);
    }

    cin >> tip;

    Parcurgere(1 , 0);

    cout << rezultat;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...