== include(page="template/taskheader" task_id="drumarb") ==
Poveste şi cerinţă...
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).
h2. Date de intrare
Fişierul de intrare $drumarb.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $drumarb.out$ ...
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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 100.000$
* $1 ≤ u, v, x, y, z, t ≤ N$
h2. Exemplu
table(example). |_. drumarb.in |_. drumarb.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|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
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="drumarb") ==
