【题目链接】:https://hihocoder.com/problemset/problem/1490

【题意】



给你一棵树的以下信息:

1.节点个数

2.给出树的每一层从左到右的顺序每个节点的编号

3.哪些节点是叶子节点

然后树中的边被去掉了;

让你复原出原图(树)

【题解】



这是道模拟题.

从最下层到上一层,从最左边的节点到右边的节点往上接父亲节点就好;

具体实现的时候;

直接找上一层最左边的且没被其他节点当爸爸的、且不为叶子节点的节点当爸爸就好;

当了爸爸之后

更新那个爸爸到其他所有节点的距离就好(不只是叶子节点,因为等会这个节点会成为新的“最底层”的节点了,你要为下一次的循环做铺垫);

然后,如果这一层里面,有和这个节点的距离为2的相邻的节点->那么它们两个可以共用一个父亲.

否则再重复找一个新的爸爸就好.



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

int n,m,k,deps[N],a[N][N],dis[N][N];

int yezi[N],fa[N],isyezi[N];

void gengxin(int x)

{

    rep1(i,1,n)

        if (dis[i][x])

            dis[i][fa[x]]=dis[fa[x]][i] = dis[i][x]-1;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    cin >> n >> m >> k;

    rep1(i,1,m)

        cin >> deps[i];

    rep1(i,1,m)

        rep1(j,1,deps[i])

            cin >> a[i][j];

    rep1(i,1,k) cin >> yezi[i],isyezi[yezi[i]] = 1;

    rep1(i,1,k)

        rep1(j,1,k)

            cin >> dis[yezi[i]][yezi[j]];

    fa[a[1][1]] = 0;

    rep2(sd,m,2)

    {

        int u = -1,pre = 0;

        rep1(i,1,deps[sd])

        {

            int v = a[sd][i];

            if (u!=-1 && dis[u][v]==2)

                fa[v] = fa[u];

            else

            {

                int idx = 1;

                rep1(j,pre+1,deps[sd-1])

                    if (!isyezi[a[sd-1][j]])

                    {

                        pre = j;

                        break;

                    }

                fa[v] = a[sd-1][pre];

                u = v;

                gengxin(v);

            }

        }

    }

    rep1(i,1,n)

    {

        cout << fa[i];

        if (i==n)

            cout << endl;

        else

            cout << ' ';

    }

    return 0;

}