思路:我们从dfs序入手。
dfs相邻的两个节点AB。可能是父子节点,可能不是父子节点。
我们主要不与bfs序,矛盾就可以了。

满足下面情况的任何一种情那么就可以说AB是父子关系。

1、bfs序A的位置+1<bfs序B的位置

2、bfs序A的位置+1=bfs序B的位置 并且 A > B //可能是兄弟姐妹(同一深度)

3、A的bfs序为1此时B一定是A的儿子

知道这些条件就能判断AB的关系,如果AB不是父子关系,那么

我们判断A的父亲与B是不是父子关系,以此类推,代码自然就需要用栈了(自己想一想问什么)

这道题考我们对bfs与dfs的认识程度,第二个条件如果只满足前面的话(A + 1 = B)的话AB可能是兄弟姐妹(同一深度),如果满足A>B那么一定不是兄弟姐妹了,因为如果是兄弟姐妹那么dfs序一定会将B放在A的前面对吧!

#include <bits/stdc++.h>
#define LL long long
using namespace std;

vector<int> son[1007];
int n, pos[1007];

int main()
{
    while(~scanf("%d", &n)){
        for(int i=0 ;i<n; i++){
            int x;
            scanf("%d", &x);
            pos[x]=i;
        }

        stack<int> s;
        int root;
        scanf("%d", &root);
        s.push(root);
        for(int i=0; i<n-1; i++){
            int x;
            scanf("%d", &x);
            while(1){
                int u=s.top();
                //可以不加第二个判断
                //bfs: 1 2 3
                //dfs: 1 2 3
                // 1 1
                // / / \
                // 2 2 3
                // /
                // 3
                //都满足条件
                /* if(pos[u]+1<=pos[x]||u==root){ son[u].push_back(x); s.push(x); break; } */
                if(pos[u]+1<pos[x]||u==root||(pos[u]+1==pos[x]&&u>x)){
                    son[u].push_back(x);
                    s.push(x);
                    break;
                }
                else{
                    s.pop();
                }
            }
        }
        for(int i=1; i<=n; i++){
            printf("%d:", i);
            sort(son[i].begin(), son[i].end());
            for(int j=0; j<son[i].size(); j++){
                printf(" %d", son[i][j]);
            }
            son[i].clear();
            printf("\n");
        }
    }

    return 0;
}
/* Sample Input 8 4 3 5 1 2 8 7 6 4 3 1 7 2 6 5 8 Sample Output 1: 7 2: 6 3: 1 2 4: 3 5 5: 8 6: 7: 8: */