Eșuând în a-și regăsi adevărata identitate, Brush se refugiază în magicul tărâm al arborilor. Arbotra o sună și îi dă următoarea problemă: se dă un arbore cu N noduri, o rădăcină fixată, și M întrebări de forma: câte perechi neordonate de noduri pot forma, luând noduri doar din subarborele nodului X (inclusiv pe X).

Cerința

Ajutați-o pe Brush să răspundă cât mai repede la intrebările lui Arbotra.

Date de intrare

Fișierul de intrare arbrush.in va conține pe prima linie trei numere naturale, numărul N, M și Root, separate de un spațiu. Următoarele N-1 linii vor conține două numere naturale a și b (între 1 și N), separate de un spațiu, cu semnificația că există muchie între nodurile a și b. Ultima linie a fișierului de intrare (linia N+1) va conține M numere separate de căte un spațiu, acestea vor semnifica cele M întrebari cerute de Arbotra.

Date de ieșire

Fișierul de ieșire arbrush.out va conține M linii, aflându-se răspunsul la fiecare întrebare cerută (în ordinea cerută în fișierul de intrare).

Restricții și precizări

2 ≤ N, M ≤ 27040
1 ≤ Root ≤ N
Uituc de fel, Arbotra poate pune aceeași întrebare de mai multe ori.

Exemplu

arbrush.in

arbrush.out

Explicație

Pentru prima întrebare, răspunsul este 3, deoarece în subarborele nodului 6 există 3 noduri: 6, 7, 8, cu care pot forma perechile {6, 7}, {7, 8}, {6, 8}

Pentru a doua întrebare răspunsul este 0, deoarece subarborele lui 4 are doar un nod, pe el înșusi și nu se pot forma perechi de câte două noduri.

Pentru a treia întrebare răspunsul este 6, deoarece în subarborele nodului 5 există 4 noduri: 5, 6, 7, 8, perechile formate sunt {6, 8}, {5, 6}, {7, 8}, {5, 8}, {5, 7}, {6, 7}

Pentru a patra întrebare răspunsul este 15.

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 Arbrush:

/*
    solutie oficiala - Potra Vlad
    complexitate : O(N+M)
*/
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

const int Nmax = 27040 + 1;
const int Mmax = 27040 + 1;

ifstream is ("arbrush.in");
ofstream os ("arbrush.out");

int N, M;
int D[Nmax];        // D[x] = marimea subarborelui lui x
int Root;
vector <int> Tree[Nmax];
bool Viz[Nmax];

void DFS(int x);

int main()
{
    is >> N >> M >> Root;
    for (int i = 1, a, b; i < N; ++i)
    {
        is >> a >> b;
        Tree[a].push_back(b);
        Tree[b].push_back(a);
    }
    DFS(Root);

    for (int i = 1, x; i <= M; ++i)
    {
        is >> x;
        os << (D[x] * (D[x]-1)) / 2 << '\n';
    }

    is.close();
    os.close();
};

void DFS(int x)
{
    Viz[x] = 1;
    D[x] = 1;
    for (const auto& y : Tree[x])
        if (Viz[y] == 0)
        {
            DFS(y);
            D[x] += D[y];
        }
};

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 #1666 Arbrush

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1666 Arbrush 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 #1666 Arbrush