题目链接如下：

Online Judge

这道题的测试数据应该很弱，因为我一开始的解法包括后来网上找到的很多题解都是有问题的，但都能AC...

下面是我看了别人解法之后写的：

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
const int maxN = 1001;
// #define debugint n, t;
int fa[maxN];
std::vector<int> dfs;
std::vector<int> follow[maxN];
std::map<int, int> locBFS;int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (scanf("%d", &n) == 1){std::fill(fa, fa + n + 1, 0);dfs.resize(n);locBFS.clear();for (int i = 1; i <= n; ++i){follow[i].clear();}for (int i = 0; i < n; ++i){scanf("%d", &t);locBFS[t] = i;}for (int i = 0; i < n; ++i){scanf("%d", &dfs[i]);}for (int i = 1; i < n; ++i){if (i == 1){fa[dfs[1]] = dfs[0];continue;}int temp = locBFS[dfs[i]];for (int j = i - 1; j >= 0; --j){if (locBFS[dfs[j]] < temp){if (locBFS[dfs[j]] == temp - 1 && dfs[j] < dfs[i]){fa[dfs[i]] = fa[dfs[j]];} else {fa[dfs[i]] = dfs[j];}break;}}}for (int i = 1; i <= n; ++i){if (fa[i]){follow[fa[i]].push_back(i);}}for (int i = 1; i <= n; ++i){printf("%d:", i);for (int j = 0; j < follow[i].size(); ++j){printf(" %d", follow[i][j]);}printf("\n");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}

我开始的解法，有问题但是能AC..

// 能AC，但有问题，hack：6 1 2 3 6 4 5 1 2 6 4 5 3
#include <cstdio>
#include <vector>
#include <map>
const int maxN = 1001;
// #define debugint n, l;
std::vector<int> bfs, dfs;
std::vector<int> son[maxN];
std::vector<int> levelVec[maxN];
std::map<int, int> locDFS;int main(){#ifdef debugfreopen("0.txt", "r", stdin);freopen("1.txt", "w", stdout);#endifwhile (scanf("%d", &n) == 1){bfs.resize(n);dfs.resize(n);locDFS.clear();for (int i = 0; i <= n; ++i){son[i].clear();levelVec[i].clear();}for (int i = 0; i < n; ++i){scanf("%d", &bfs[i]);}for (int i = 0; i < n; ++i){scanf("%d", &dfs[i]);locDFS[dfs[i]] = i;}levelVec[0].push_back(bfs[0]);l = 1;for (int i = 1; i < n; ++i){if (locDFS[bfs[i]] < locDFS[bfs[i - 1]]){l++;}levelVec[l].push_back(bfs[i]);}for (int i = 0; i < l; ++i){int k = 0;for (int j = 1; j < levelVec[i].size(); ++j){int temp = locDFS[levelVec[i][j]];while (k < levelVec[i + 1].size() && locDFS[levelVec[i + 1][k]] < temp){son[levelVec[i][j - 1]].push_back(levelVec[i + 1][k]);k++;}}while (k < levelVec[i + 1].size()){son[levelVec[i].back()].push_back(levelVec[i + 1][k]);++k;}}for (int i = 1; i <= n; ++i){printf("%d:", i);for (int j = 0; j < son[i].size(); ++j){printf(" %d", son[i][j]);}printf("\n");}}#ifdef debugfclose(stdin);fclose(stdout);#endifreturn 0;
}