4256번: 트리

https://www.acmicpc.net/problem/4256


$O(tn)$

http://codedoc.tistory.com/779와 유사하다.

#include<cstdio>
int t, n, a[1001], bi[1001];
void f(int al, int ar, int bl, int br) {
    if (al > ar) return;
    int m = bi[a[al]];
    f(al + 1, al + m - bl, bl, m - 1);
    f(al + m - bl + 1, ar, m + 1, br);
    printf("%d ", a[al]);
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        for (int i = 1, x; i <= n; i++) scanf("%d", &x), bi[x] = i;
        f(1, n, 1, n);
        puts("");
    }
    return 0;
}