P4006 小 Y 和二叉树

· · 题解

挺有意思一道题。提供一种更方便理解(?)的做法。

要求字典序最小，我们可以贪心地确定第一个数，即满足度数 \leq 2 的编号最小的节点。

设这个节点为 u，将 u 钦定为最左边的节点，先讨论 u 度数为 2 的情况，那么与他相连的两个节点，一个是右儿子 v，一个是父亲 f。

先不考虑字典序最小。

此时我建出一颗新的树，u 为根节点，让 v 为 u 的左儿子，f 为 u 的右儿子，其余的关系不变。若将在 u 处的遍历顺序设置为前序遍历，那么在 u 处就会按照 u - v - w 的顺序遍历。那么在 u 处这其实和原树的遍历顺序是相同的。

回到原树，v 是 u 的儿子，那么在 v 的子树中应该是中序遍历，这点在新树上也一样，故新树上 v 及其子树都采取中序遍历。

而 f 是 u 的父亲，当原树遍历完 u 和 v 的子树之后，它们就不影响后面的中序遍历的，可以删去。删去之后，f 的情况就和 u 相同了，即都被钦定为最左边的节点。这是一个子问题，让 f 成为新的 u，递归解决。

再是度数为 1 的情况，与 u 相连的节点为 w，那么 w 成为新树上 u 的左儿子，在原树上 w 就是 u 的右儿子；w 成为新树上 u 的右儿子，在原树上 w 就是 u 的父亲。

所以总的策略就是：先将 u 提为根节点；然后新树按照如下规则 dfs：

可以证明这样形成的遍历序列就是原树的中序遍历序列。

下面考虑怎么使字典序更小。即如何安排新树上的左右儿子。

先以 u 为根，求出 dp_x 为 x 的子树内度数 \leq 2 的编号最小的节点编号。

然后 dfs 过程中分类讨论，当前节点为 x：

若新树上 x 有 1 个儿子 s，那么如果 dp_s < s 就将 s 作为新树上 x 的左儿子，否则作为 x 的右儿子。

若新树上 x 有 2 个儿子 s_1, s_2，那么如果 dp_{s_1} < dp_{s_2} 那么将 s_1 作为新树上 x 的左儿子，s_2 作为 x 的右儿子。否则 s_2 作为左儿子，s_1 作为右儿子。

若新树上 x 有 1 个儿子 s，那么如果 dp_s < x 就将 s 作为 x 的左儿子，否则作为 x 的右儿子。

若新树上 x 有 2 个儿子 s_1, s_2，那么如果 dp_{s_1} < dp_{s_2} 则将 s_1 作为新树上 x 的左儿子，s_2 为右儿子。否则 s_2 为左儿子，s_1 为右儿子。

容易证明这样贪心是正确的。按照顺序输出即可。

#include<cstdio>
#include<vector>
#include<algorithm>
const int M=1e6+10;
const int inf=1e9+7;

int n,rt,deg[M],f[M];
std::vector<int>g[M];

void dfs(int u,int fa,bool type){
    // type = 0 : 前序遍历
    // type = 1 : 中序遍历
    std::vector<int>nxt;
    for(int v:g[u])
        if(v!=fa) nxt.push_back(v);
    if(!type){
        // 根 - 左子树 - 右子树
        printf("%d ",u);
        if(nxt.size()==1){
            if(f[nxt[0]]<nxt[0]){
                dfs(nxt[0],u,1);
            }else{
                dfs(nxt[0],u,0);
            }
        }else if(nxt.size()==2){
            if(f[nxt[0]]<f[nxt[1]]){
                dfs(nxt[0],u,1);
                dfs(nxt[1],u,0);
            }else{
                dfs(nxt[1],u,1);
                dfs(nxt[0],u,0);
            }
        }
    }else{
        // 左子树 - 根 - 右子树
        if(nxt.size()==0){
            printf("%d ",u);
        }else if(nxt.size()==1){
            if(f[nxt[0]]<u){
                dfs(nxt[0],u,1);
                printf("%d ",u);
            }else{
                printf("%d ",u);
                dfs(nxt[0],u,1);
            }
        }else if(nxt.size()==2){
            if(f[nxt[0]]<f[nxt[1]]){
                dfs(nxt[0],u,1);
                printf("%d ",u);
                dfs(nxt[1],u,1);
            }else{
                dfs(nxt[1],u,1);
                printf("%d ",u);
                dfs(nxt[0],u,1);
            }
        }
    }
}

void dp(int u,int fa){
    f[u]=(deg[u]<=2?u:inf);
    for(int v:g[u]){
        if(v==fa) continue;
        dp(v,u);
        f[u]=std::min(f[u],f[v]);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&deg[i]);
        for(int j=1,x;j<=deg[i];j++){
            scanf("%d",&x);
            g[i].push_back(x);
        }
        if(deg[i]<=2&&!rt) rt=i;
    }
    dp(rt,0);
    dfs(rt,0,0);
    return 0;
}