Cerința

În țara lui Zoli trăiesc n persoane, numerotate de la 1 la n, iar Zoli are numărul de ordine 1. Zoli s-a săturat de sistemul politic, așa că s-a decis să iasă în stradă. Deoarece Zoli este o persoană sociabilă, are prieteni din diverse cercuri pe care s-a gândit să îi cheme cu el. Zoli își va anunța prietenii, care la rândul lor își vor anunța prietenii și așa mai departe.

Știm însă că unele persoane sunt scandalagii, iar Zoli este un om pașnic și preferă să nu trimită invitația acestora.

Zoli vă cere să îi spuneți numărul de persoane cu care se va întâlni la protest.

Date de intrare

Fișierul de intrare protest.in conține pe prima linie numărul n, reprezentând numărul de prieteni și numărul k, reprezentând numărul de prieteni scandalagii.

A doua linie conține k numere, reprezentând numerele de ordine ale prietenilor scandalagii.

Următoarele n-1 linii vor conține câte două perechi de numere x y cu semnificația că persoana cu numărul de ordine x este prietenă cu persoana ce are numărul de ordine y.

Date de ieșire

Fișierul de ieșire protest.out va conține doar numărul nr, reprezentând numărul de prieteni care i se vor alătura lui Zoli.

Restricții și precizări

1 ≤ n ≤ 50000
1 ≤ k ≤ 1000
Numerele de ordine ale scandalagiilor vor fi mai mici decât n
Fiecare persoană poate anunța doar prietenii cu care are o legătură directă, rămânând pe seama celor din urmă să transmită invitația mai departe, dacă e posibil.
Relația de prietenie nu este reciprocă.

Exemplu

protest.in

protest.out

Explicație

Zoli va anunța prietenii cu numerele de ordine 2 și 6.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Protest:

#include <fstream>
#include <vector>

using namespace std;

ifstream fin("protest.in");
ofstream fout("protest.out");

const int MaxN = 100001;

vector<int> G[MaxN];
vector<bool> scandalagiu;
vector<bool> viz;

int n, k, nr;

void Df(int nod);

int main()
{
    fin >> n >> k;

    scandalagiu = vector<bool>(n + 1);
    viz         = vector<bool>(n + 1);

    for ( int i = 1, sc; i <= k; ++i )
    {
        fin >> sc;
        scandalagiu[sc] = 1;
    }

    for ( int i = 1, x, y; i < n; ++i )
    {
        fin >> x >> y;
        G[x].push_back(y);
    }

    Df(1);

    fout << nr;


    fin.close();
    fout.close();
    return 0;
}

void Df(int nod)
{
    viz[nod] = 1;

    for ( auto v : G[nod] )
    {
        if ( !scandalagiu[v] && !viz[v] )
        {
            Df(v);
            nr++;
        }

    }


}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1341 Protest

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1341 Protest de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1341 Protest