Loj #2324. 「清华集训 2017」小 Y 和二叉树

柔情只为你懂 2022-10-03 00:37 145阅读 0赞

# Loj \#2324. 「清华集训 2017」小 Y 和二叉树 #

小Y是一个心灵手巧的OIer，她有许多二叉树模型。

小Y的二叉树模型中，每个结点都具有一个编号，小Y把她最喜欢的一个二叉树模型挂在了墙上，树根在最上面，左右子树分别在树根的左下方与右下方，且他们也都满足

这样的悬挂规则。为了让这个模型更加美观，小Y选择了一种让这棵二叉树的中序遍历序列最小的悬挂方法。所谓中序遍历最小，就是指中序遍历的结点编号序列的字典

序最小。

一天，这个模型不小心被掉在了地上，幸运的是，所有结点和边都没摔坏，但是她想不起这个模型原来是怎么悬挂的了，也就是说：她想不起来树根节点的编号了。

小Y最近忙于准备清华集训，所以没太多时间处理别的事情，她只好找到同样心灵手巧的你帮忙复原她的二叉树模型。

给定小Y的二叉树模型，结点的编号为 \\(1\\) ~ \\(n\\) ，你需要给出其可能的最小的中序遍历，方便小Y更快的摆好她的模型。

### 输入格式 ###

第一行为一个正整数 \\(n\\) ，表示点的个数。

后接 \\(n\\) 行，每行若干个整数：

第 \\(i+1\\) 行的第一个整数为 \\(k\_i\\) ，表示编号为 \\(i\\) 的结点的度数，后接 \\(k\_i\\) 个整数 \\(a\_\{i,j\}\\) ，表示编号为 \\(i\\) 的结点与编号为 \\(a\_\{i,j\}\\) 的结

点之间有一条边。

同一行输入的相邻两个元素之间，用恰好一个空格隔开。

### 输出格式 ###

输出共一行， \\(n\\) 个整数，表示字典序最小的中序遍历。

### 数据范围与提示 ###

\\(n\\leq 10^6\\)

假设我们知道了最优答案下的根，那么答案就很好求了。

设\\(mn\_i\\)表示\\(i\\)的子树的中序遍历得到第一个点。我们可以发现，\\(mn\_i\\)就是\\(i\\)子树中度数\\(\\leq 2\\)的子节点中最小的那个。然后我们就递归：如果一个点有两个儿子，就优先走\\(mn\\)值小的那个；如果只有一个儿子，就要判断儿子的\\(mn\\)值是否比自己的值大来判断将儿子放在左边还是右边。

难点就是找根。很容易发现，答案的第一位一定是度数\\(\\leq 2\\)的节点中最小的那个。然后我们从这个点开始递归，找到最终答案下的根。我们先找到最小的点，设为\\(g\\)。然后以\\(g\\)为根，求出\\(mn\\)数组。接着就是分情况讨论：

假设当前处理\\(v\\)节点。默认与\\(v\\)相邻的还没有访问到的点为\\(v\\)的儿子。

*  情况1：

假设\\(v\\)只有一个儿子\\(sn\_1\\)，若 \\(sn\_1\\leq mn\_\{sn\_1\}\\) 则 \\(sn\_1\\) 就作为\\(v\\)的父亲，递归\\(sn\_1\\)；否则\\(v\\)就是最终的根。  
如果\\(sn\_1\\)不作为\\(v\\)的父亲，那么最终答案里，\\(v\\)过了就是\\(mn\_\{sn\_1\}\\)；反之\\(v\\)过了就是\\(sn\_1\\)。所以这个贪心是正确的。

*  情况2：

假设\\(v\\)有两个儿子\\(sn\_1\\),\\(sn\_2\\)（不妨设\\(mn\_\{sn\_1\}<mn\_\{sn\_2\}\\)）。那么将\\(sn\_1\\)作为右儿子，\\(sn\_2\\)作为父亲，递归\\(sn\_2\\)。

#include<bits/stdc++.h>
    #define ll long long
    #define N 1000005
    
    using namespace std;
    inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
    
    int n;
    int r[N];
    struct road {
        int to,nxt;
    }s[N<<1];
    int h[N],cnt;
    void add(int i,int j) {s[++cnt]=(road) {j,h[i]};h[i]=cnt;}
    
    vector<int>ans;
    int rt;
    bool vis[N];
    int mn[N];
    
    void Get_mn(int v,int fr) {
        if(r[v]<3) mn[v]=v;
        else mn[v]=1e9;
        for(int i=h[v];i;i=s[i].nxt) {
            int to=s[i].to;
            if(to==fr) continue ;
            Get_mn(to,v);
            mn[v]=min(mn[v],mn[to]);
        }
    }
    
    int RT;
    void Find_rt(int v,int fr) {
        int sn1=0,sn2=0;
        for(int i=h[v];i;i=s[i].nxt) {
            int to=s[i].to;
            if(to==fr) continue ;
            if(!sn1) sn1=s[i].to;
            else sn2=s[i].to;
        }
        if(!sn1) {RT=v;return ;}
        if(!sn2) {
            if(sn1<=mn[sn1]) Find_rt(sn1,v);
            else {RT=v;return ;}
        } else {
            if(mn[sn1]>mn[sn2]) swap(sn1,sn2);
            Find_rt(sn2,v);
        }
    }
    
    void Print(int v,int fr) {
        int sn1=0,sn2=0;
        for(int i=h[v];i;i=s[i].nxt) {
            int to=s[i].to;
            if(to==fr) continue ;
            if(!sn1) sn1=to;
            else sn2=to;
        }
        if(mn[sn1]>mn[sn2]) swap(sn1,sn2);
        if(!sn2&&mn[sn1]>v) swap(sn1,sn2);
        if(sn1) Print(sn1,v);
        cout<<v<<" ";
        if(sn2) Print(sn2,v);
    }
    
    int main() {
        mn[0]=1e9;
        n=Get();
        for(int i=1;i<=n;i++) {
            int k=Get();
            r[i]=k;
            while(k--) {
                int a=Get();
                add(i,a);
            }
        }
        rt=1e9;
        for(int i=1;i<=n;i++) if(r[i]!=3) rt=min(rt,i);
        Get_mn(rt,0);
        Find_rt(rt,0);
        Get_mn(RT,0);
        Print(RT,0);
        return 0;
    }

转载于:https://www.cnblogs.com/hchhch233/p/10731571.html