Consideremos un árbol enraizado con raíz en el vértice 1, donde un árbol es un grafo conectado sin ciclos ni múltiples aristas. El árbol está orientado con la raíz hacia arriba, lo cual es común en estructuras de datos para programadores.

En este árbol, dos manzanas crecerán en vértices específicos (pueden ser el mismo vértice). Después, se sacude el árbol hasta que las manzanas caen. Cada sacudida ocasiona lo siguiente para cada manzana en el vértice u:

• Si u tiene un hijo, la manzana se mueve a él (en caso de múltiples hijos, se elige cualquiera).
• De lo contrario, la manzana cae del árbol.

Se garantiza que ambas manzanas caerán eventualmente. Dado q suposiciones sobre los vértices donde crecen las manzanas (x e y), se debe calcular el número de pares ordenados de vértices (a, b) donde a es el vértice de caída de la manzana desde x, y b es el vértice de caída desde y.

Entrada

La primera línea cnotiene t (1 ≤ t ≤ 10^4), el número de casos de prueba. Para cada caso:

• Una línea con n (2 ≤ n ≤ 2·10^5), el número de vértices.
• n-1 líneas describiendo las aristas, cada una con u_i y v_i (1 ≤ u_i, v_i ≤ n).
• Una línea con q (1 ≤ q ≤ 2·10^5), el número de suposiciones.
• q líneas con x_i e y_i (1 ≤ x_i, y_i ≤ n).

La suma de n y q no excede 2·10^5 en todos los casos.

Salida

Para cada suposición, imprimir en una línea separada el número de pares ordenados de vértices donde las manzanas pueden caer.

Ejemplos

Ejemplo 1

Entrada:

2
5
1 2
3 4
5 3
3 2
4
3 4
5 1
4 4
1 3
3
1 2
1 3
3
1 1
2 3
3 1

Salida:

2
2
1
4
4
1
2

Ejemplo 2

Entrada:

2
5
5 1
1 2
2 3
4 3
2
5 5
5 1
5
3 2
5 3
2 1
4 2
3
4 3
2 1
4 2

Salida:

1
2
1
4
2

Explicación

En el primer ejemplo, para la primera suposición, los pares posibles son (4,4) y (5,4). Para la segunda, son (5,4) y (5,5). Para la tercera, solo (4,4). Para la cuarta, hay cuatro pares: (4,4), (4,5), (5,4), (5,5).

La solución implica calcular el número de hojas en el subárbol de cada vértice. Una hoja es un vértice sin hijos. Para un vértice u, sea count[u] el número de hojas en su subárbol. Entonces, si las manzanas crecen en x e y, el número de pares ordenados es count[x] * count[y], ya que cada manzana puede caer desde cualquier hoja en su subárbol.

Implementación en C++

El siguiente código calcula el conteo de hojas usando DFS (Búsqueda en Profundidad). Se reescribe con nombres de variables y estructura modificados para mantener la corrección.

#include <iostream>
#include <vector>
using namespace std;

void calcularHojas(int nodo, int padre, const vector<vector<int>>& arbol, vector<int>& conteoHojas) {
    bool esHoja = true;
    for (int hijo : arbol[nodo]) {
        if (hijo != padre) {
            esHoja = false;
            calcularHojas(hijo, nodo, arbol, conteoHojas);
            conteoHojas[nodo] += conteoHojas[hijo];
        }
    }
    if (esHoja) {
        conteoHojas[nodo] = 1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int casos;
    cin >> casos;
    while (casos--) {
        int vertices;
        cin >> vertices;
        vector<vector<int>> arbol(vertices + 1);
        for (int i = 0; i < vertices - 1; ++i) {
            int u, v;
            cin >> u >> v;
            arbol[u].push_back(v);
            arbol[v].push_back(u);
        }

        vector<int> conteoHojas(vertices + 1, 0);
        calcularHojas(1, 0, arbol, conteoHojas);

        int consultas;
        cin >> consultas;
        while (consultas--) {
            int x, y;
            cin >> x >> y;
            cout << conteoHojas[x] * conteoHojas[y] << '\n';
        }
    }
    return 0;
}

Este código utiliza una lista de adyacencia con vectores y una DFS recursiva para contar hojas. Se modifica la estructura para mayor claridad, manteniendo la lógica esencial.