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

8 4 1
1 2
2 3
2 5
5 6
6 7
6 8
1 4
6 4 5 2

arbrush.out

3
0
6
15

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.

#include <bits/stdc++.h>


using namespace std;

ifstream cin("arbrush.in");
ofstream cout("arbrush.out");

vector <int> G[30001];
int n ,m  , p , x , y , k , P[30001] , d[30001] , r;

int dfs(int x)
{
    P[x] = 1;
    d[x] = 1;
    for(auto i:G[x])
        if(!P[i]) d[x] += dfs(i);
    return d[x];

}

int main()
{
    cin >> n >> m >> r;
    for(int i = 1 ; i < n ; i++)
    {
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    d[r] = dfs(r);
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x;
        cout << d[x] * (d[x] - 1) / 2 << '\n';
    }
}