Fişierul intrare/ieşire:drumarb.in, drumarb.outSursăAdobe - Code Pandas
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.indrumarb.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?