keidei

Algoritmul, pas cu pas

Ideea de pornire e simplă: nu desenăm toate ordonările posibile ale fiilor (ar fi mult prea multe). În schimb, pentru fiecare nod $v$ ne întrebăm direct: câte noduri pot ajunge înaintea lui în parcurgere? Dacă printre acele numere posibile apare $K-1$, atunci $v$ poate fi exact al $K$-lea, adică pe poziția $K$.

Cheia e că „numărul de noduri dinaintea lui $v$" nu e fix — depinde de cum aranjăm frații. Dar nu poate fi orice: e o sumă de submulțime a unor blocuri întregi (subarbori frați la DFS, grupuri de pe nivel la BFS), pe care le putem pune înainte sau după ramura spre $v$. Asta transformă problema într-un subset-sum, pe care îl ținem compact cu bitset-uri.