HackerEarth Restoring trees problem solution YASH PAL, 31 July 2024 In this HackerEarth Restoring trees problem solution You are given the start and finish times of a DFS (Depth-first search) traversal of the vertices that are available in a rooted tree. Your task is to restore the tree. HackerEarth Restoring trees problem solution #include<bits/stdc++.h>using namespace std;const int N = 300005;int n, st[N], fn[N], rev[N], P[N];void Solve(int v){ int nw = st[v] + 1; int u = rev[nw]; for (; nw < fn[v]; nw = fn[u], u = rev[nw]) P[u] = v, Solve(u);}int main(){ scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &st[i]), rev[st[i]] = i; for (int i = 1; i <= n; i++) scanf("%d", &fn[i]); Solve(rev[0]); for (int i = 1; i <= n; i++) printf("%d ", P[i]); printf("n"); return (0);} Second solution #include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 3e5 + 14;int n, st[maxn], en[maxn], per[maxn], ans[maxn];int main(){ ios::sync_with_stdio(0), cin.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> st[i]; for(int i = 0; i < n; i++) cin >> en[i]; iota(per, per + n, 0); sort(per, per + n, [](int i, int j){ return st[i] < st[j]; }); int p = -1; for_each(per, per + n, [&p](int &i){ while(p != -1 && en[p] < en[i]) p = ans[p]; ans[i] = p; p = i; }); for(int i = 0; i < n; i++) cout << ans[i] + 1 << ' '; cout << 'n';} coding problems