| Fişierul intrare/ieşire: | drumarb.in, drumarb.out | Sursă | Adobe - Code Pandas |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Drumarb
Se da un arbore cu N noduri, numerotate de la 1 la N. Se mai dau si M intrebari la care trebuie sa raspundeti. O intrebare este specificata prin 4 noduri din arbore, x, y, z si t, si cere determinarea numarului de noduri care se afla atat pe drumul de la x la y, cat si pe drumul de la z la t (altfel spus, trebuie sa determinati cate noduri fac parte din intersectia drumurilor x-y si z-t in arbore).
Date de intrare
Pe prima linie a fisierului de intrare drumarb.in se afla 2 numere intregi, N si M, separate printr-un spatiu. Pe urmatoarele N-1 linii se afla cate 2 numere u si v, separate printr-un spatiu, avand semnificatia ca exista o muchie intre nodul u si nodul v in arbore. Pe urmatoarele M linii se afla cate 4 numere intregi, separate prin cate un spatiu, x, y, z si t, specificand cate o intrebare.
Date de ieşire
In fisierul de iesire drumarb.out veti afisa raspunsul la fiecare din cele M intrebari, in ordinea in care acestea sunt date in fisierul de intrare. Fiecare raspuns va fi afisat pe o linie separata.
Restricţii
- 1 ≤ N ≤ 100.000
- 1 ≤ M ≤ 100.000
- 1 ≤ u, v, x, y, z, t ≤ N
Exemplu
| drumarb.in | drumarb.out |
|---|---|
| 11 5 1 2 2 4 4 5 4 6 6 7 2 8 1 3 3 9 10 9 11 9 5 11 6 10 3 10 8 4 9 2 5 7 9 4 5 7 5 11 8 7 | 5 0 0 1 2 |
