Fişierul intrare/ieşire:	disconnect.in, disconnect.out	Sursă	Algoritmiada 2015 Runda 1
Autor	Adrian Vladu	Adăugată de	Adrian Budau •freak93
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

Disconnect

Fie T un arbore neorientat cu N noduri. Vom aplica asupra lui M operaţii de tipul:

1 x y Se şterge muchia x-y din arbore.
2 x y Se pune întrebarea "Există drum in arbore de la nodul x la nodul y?"

Cerinţa este ca programul vostru să afişeze răspunsul corect pentru toate operaţiile de tip 2.

Date de intrare

Fişierul de intrare disconnect.in va conţine pe prima linie numerele N şi M, semnificând numărul de noduri, respectiv numărul de operaţii care se vor efectua asupra arborelui. Următoarele N - 1 linii conţin câte o pereche de numere X Y, semnificând faptul că există o muchie neorientată între nodurile X şi Y. Următoarele M linii conţin câte trei numere tip X Y. Numărul tip denotă tipul operaţiei, fiind egal cu 1 dacă este vorba de o ştergere sau 2 dacă e vorba de o întrebare. Numerele X şi Y vor fi folosite pentru a genera nodurile pe care se va aplica operaţia respectivă. Mai exact, aceste noduri vor fi A = X xor V şi B = X xor V unde V este o variabila iniţial egală cu 0. După fiecare operaţie de tip 2 variabila V îşi va schimba valoarea în A (dacă răspunsul la întrebare a fost pozitiv), respectiv în B (dacă acesta a fost negativ). Vă oferim un fragment de cod în C++ care generează şi rezolvă operaţiile.

int V = 0;

    for (int i = 0; i < M; ++i) {
        int type, x, y; cin >> type >> x >> y;

        int a = x xor V;
        int b = y xor V;

        if (type == 1) {
            removeEdge(a, b);
        } else
            if (query(a, b)) {
                cout << "YES\n";
                V = a;
            } else {
                cout << "NO\n";
                V = b;
            }
    }

Date de ieşire

Fişierul de ieşire disconnect.out va conţine câte o linie pentru fiecare operaţie de tip 2. Linia va conţine YES dacă răspunsul este pozitiv şi NO altfel.

Restricţii

• 1 ≤ N ≤ 200 000
• 1 ≤ M ≤ 500 000
• Pentru 20% din punctaj testele respectă restricţia 1 ≤ N ≤ 1 000, 1 ≤ M ≤ 5 000
• Pentru 40% din punctaj testele respectă restricţia 1 ≤ N ≤ 10 000, 1 ≤ M ≤ 500 000

Exemplu

Explicaţie

...

Cum se trimit solutii?