copac

Enunț

Se consideră un arbore cu $N$ noduri numerotate de la $1$ la $N$, dintre care $K$ sunt frunze (noduri cu gradul $1$). Frunzele poartă numerele de ordine de la $1$ la $K$.

Despre acest arbore nu se cunosc alte informaţii dar, din fericire, se pot adresa întrebări de tipul “care este distanţa de la frunza $x$ la frunza $y$?”. Distanţa dintre două noduri din arbore este egală cu numărul de muchii aflate pe lanţul elementar ce uneşte cele două noduri.

Cerință

Determinaţi arborele punând cel mult $12\ 000$ întrebări.

Protocol de interacțiune

Programul vostru nu va citi şi nu va scrie nici un fişier. În schimb, va trebui să implementați funcția

std::vector<int> solve(int K);

care primește ca parametru numărul de frunze $K$ și returnează vectorul de tați al arborelui (nu contează care nod este considerat rădăcină). Pentru a determina arborele, puteți apela funcția

int query(int x, int y);

unde $x$ şi $y$ sunt numere întregi distincte cuprinse între $1$ şi $K$, funcția returnând distanța dintre nodurile $x$ și $y$.

Exemplu

• Comisia apelează solve(3).
• Concurentul apelează query(1, 2) care returnează 3.
• Concurentul apelează query(2, 3) care returnează 3.
• Concurentul apelează query(1, 3) care returnează 2.
• Funcția solve returnează {4, 5, 4, 0, 4}.

Restricții și precizări

• $3 \leq K \leq 3 \ 000$;
• Numărul de noduri din arborele rezultat nu va depăşi $10\ 000$.
• Dacă programul nu respectă interacţiunea stabilită, va lua $0$ puncte pe testul respectiv.
• Trebuie să includeți copac.h