【树】2020ICPC小米网赛1G-Tree Projection

传送门

题意是说给一颗树的拓扑序列,再给它的dfs序列。两次根可能不同。

问你能不能构造出原树。

首先要分析两种序列的性质。

拓扑序和dfs序,排在后面的点肯定是前面的点的子孙。所以后面的点与前面的点连边不能超过1条。

那么有个很简单的想法:

使得两个序列都满足每个点与前面出现的点最多有一条边。

然而很遗憾这是不对的。下面给出一个反例

top:6 4 2 1 3 5

dfs:1 2 3 4 5 6

很显然这样一种构造只能满足拓扑序,不能满足dfs序。

要满足dfs序,还需要满足要满足一个条件:一个点要么是叶子(与后面不连边),要么是某个子树的根(必须与紧接着后面的一个点连边)。

所以需要构造一棵合法的树,每个序列的节点要满足两个两个条件:1. 每个点最多与前面一个点相连。 2. dfs序中的每个点还要满足要么后面挨着的一个点与他相连,要么后面没有点和他相连。

具体做的时候,两个指针i, j枚举dfs序,每次由B[j]向B[i]连边,保证 i < j 而且 i 在过程中单调不减,即可让dfs序列满足条件。同时让B[i]在A中的位置单调不增,即可让拓扑序满足第一个条件。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N = 2e5 + 233;
int a[N], b[N], pos[N];
int main()
{
    // time_t startt = clock();

    // cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i;
    for(int i = 1; i <= n; i++) cin >> b[i];

    puts("YES");
    for(int i = 2, j = b[1]; i <= n; i++)
    {
        printf("%d %d\n", b[i], j);
        if(pos[b[i]] < pos[j]) j = b[i];
    }

    // cerr << "~ #" << " done! time : " << (double)(clock()-startt) << " ms" << endl;
    // cerr << "~ #" << " done! time : " << (double)(clock()-startt)/CLOCKS_PER_SEC << " s" << endl;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注