题解：P4006 小 Y 和二叉树

_Ch1F4N_ · 2024-05-04 12:38:47 · 题解

构造题。

考虑最小化第一个中序遍历的点，这个点一定没有左儿子故其度数不大于 2，取最小的点即可。

然后递归构造，具体而言假设当前点为 u，假设其出边集合为 E 需要决定哪些点放儿子哪些放父亲，具体而言需要对一个子树求出以其为根的子树中序遍历最小是多少，这个可以用一次树形 dp 简单的解决，考虑在在第一次需要 dp 时以其为根，那么其余时候需要询问的联通子图答案一定是以这个树的一个节点为根的子树，这是根据其儿子信息合并的结果以及其目前的度数更新 dp 信息即可。

注意按位贪心，优先最小化右儿子再处理父亲。

时间复杂度是 O(n) 的，对每个点的出边排序是 \log 3 也就是常数级别的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+114;
vector<int> E[maxn];
int n;
int Fir;
bool flag=false;
int Min[maxn],son[maxn];
void init(int u,int fa){
    Min[u]=maxn+1;
    son[u]=maxn+1;
    for(int v:E[u]){
        if(v!=fa){
            init(v,u);
            Min[u]=min(Min[u],Min[v]);
        }
    }
    son[u]=Min[u];
    if(E[u].size()<=2) Min[u]=min(Min[u],u);
}
void Out(int u){
    if(E[u].size()==0){
        cout<<u<<" ";
        return ;
    }else if(E[u].size()==1){
        int v=E[u].back();
        E[u].pop_back();
        E[v].erase(lower_bound(E[v].begin(),E[v].end(),u));
        Min[v]=son[v];
        if(E[v].size()<=1) Min[v]=min(Min[v],v);
        if(Min[v]<u){
            Out(v);
            cout<<u<<" ";
        }else{
            cout<<u<<" ";
            Out(v);
        }
    }else{
        int v1=E[u].back();
        E[u].pop_back();
        E[v1].erase(lower_bound(E[v1].begin(),E[v1].end(),u));
        int v2=E[u].back();
        E[u].pop_back();
        E[v2].erase(lower_bound(E[v2].begin(),E[v2].end(),u));
        Min[v1]=son[v1];
        if(E[v1].size()<=1) Min[v1]=min(Min[v1],v1);
        Min[v2]=son[v2];
        if(E[v2].size()<=1) Min[v2]=min(Min[v2],v2);
        if(Min[v1]>Min[v2]) swap(v1,v2);
        Out(v1);
        cout<<u<<" ";
        Out(v2);
    }
}
void calc(int u){
    init(u,0);
    Out(u);
}

void solve(int u){
    cout<<u<<' ';
    if(E[u].size()==0) return ;
    if(E[u].size()==1){
        int v=E[u].back();
        E[u].pop_back();
        E[v].erase(lower_bound(E[v].begin(),E[v].end(),u));
        if(flag==false){
            flag=true;
            init(v,0);
        }
        Min[v]=son[v];
        if(E[v].size()<=1) Min[v]=min(Min[v],v);
        if(v<Min[v]) solve(v);
        else calc(v);
    }else{
        int v1=E[u].back();
        E[u].pop_back();
        E[v1].erase(lower_bound(E[v1].begin(),E[v1].end(),u));
        int v2=E[u].back();
        E[u].pop_back();
        E[v2].erase(lower_bound(E[v2].begin(),E[v2].end(),u));
        if(flag==false){
            flag=true;
            init(v1,0);
            init(v2,0);
        }        
        Min[v1]=son[v1];
        if(E[v1].size()<=1) Min[v1]=min(Min[v1],v1);
        Min[v2]=son[v2];
        if(E[v2].size()<=1) Min[v2]=min(Min[v2],v2);
        if(Min[v1]>Min[v2]) swap(v1,v2); 
        calc(v1);
        solve(v2);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    Fir=n+1;
    for(int i=1;i<=n;i++){
        int d;
        cin>>d;
        for(int j=1;j<=d;j++){
            int v;
            cin>>v;
            E[i].push_back(v);
        }
        if(d!=3){
            Fir=min(Fir,i);
        }
        sort(E[i].begin(),E[i].end());
    }
    solve(Fir);
    return 0;
}