Here's a solution for Genokraken.

Since $$$1$$$ has degree $$$2$$$, let its descendent be $$$k>1$$$. Value $$$k$$$ can be found as the first query in $$$(1,2), (1,3), (1,4), \ldots$$$ that returns 0. This takes at most $$$n-2$$$ queries. Now $$$p_k=1$$$, so for $$$k<i<n$$$ node $$$i$$$ has $$$pᵢ\geq 1$$$, and in particular $$$pᵢ\neq 0$$$. Therefore, the number of paths is $$$k-1$$$. Furthermore, for $$$k<i≤j<n$$$ we have $$$pᵢ≤pⱼ$$$, but also $$$pᵢ≠pⱼ$$$, since only the root has several descendants, so $$$pᵢ=pⱼ$$$ implies $$$pᵢ=pⱼ=0$$$, which is excluded. Thus $$$pᵢ<pⱼ$$$, and the parent sequence increases. So to place node $$$i$$$ for $$$k<i<n$$$, we take the first query in $$$(i,p)$$$ for $$$p=2,3,\ldots$$$ that returns $$$0$$$, set $$$pᵢ=p$$$, increase $$$i$$$ and $$$p$$$ and repeat. Note that $$$p$$$ never decreases, so this takes again at most $$$n-2$$$ queries, and overall we need at most $$$2n-4$$$ queries. The resulting code (where same returns true if the query returns 0) essentially is:

vector<int> p(n, 0);
int i = 2;
while (!same(1, i))
  i++;
p[i] = 1;

i++;
int j = 2;
while (i < n) {
  while (!same(i, j))
    j++;
  p[i] = j;
  i++;
  j++;
}

(Submission 302894231)