CodeForces 1228F One Node is Gone

洛谷题目页面传送门 & codeforces题目页面传送门

给定一棵树\(t=(v,e),|v|=2^n-2,|e|=2^n-3\)，输出所有的\(x\)，使得存在一棵满二叉树\(t'\)，将\(t'\)中节点\(x\)的一个儿子删除并把这个儿子的所有儿子接到\(x\)下后等于\(t\)。升序输出。

\(n\le17\)。

题目没有说以哪个点为根，也就是每个点都有可能是根，很自然地想到可以二次扫描与换根。先考虑选一个点作为根，那显然满足条件的改补的节点的父结点最多有\(1\)个。这个父结点可以dp出来。

我们将一个子树分类讨论：

1. 是一棵满二叉树。设它的深度为\(d\)，则记这颗子树的特征为有序对\((0,d)\)。这种情况发生当且仅当它有\(2\)棵子树并且都是矮\(1\)层的满二叉树。特殊地，如果它的大小为\(1\)，则它的特征为\((0,1)\)。

2. 还原一个节点之后为满二叉树。设还原之后的深度为\(d\)，补的节点的父结点为\(x\)，则记这棵子树的特征为有序对\((x,d)\)。这种情况发生当且仅当以下任意一个条件为真：

   1. 它的根为\(x\)，有\(1\)棵子树并且这棵子树大小为\(1\)，此时应将改补的节点直接补在\(x\)下。
   2. 它的根为\(x\)，有\(3\)棵子树并且其中\(1\)棵为矮\(1\)层的满二叉树，另\(2\)棵为矮\(2\)层的满二叉树，此时应将改补的节点补在\(x\)下并将\(2\)棵矮\(2\)层的字树接在改补的节点下。
   3. 它有\(2\)棵子树并且一棵为矮\(1\)层的满二叉树，另一颗补一个父结点为\(x\)的节点之后为满二叉树。

3. 不管补不补节点都不能成为满二叉树。记它的特征为有序对\((-1,-1)\)。显然，不满足\(1,2\)则为此种情况。

设\(dp_i\)为以\(1\)为根时以\(i\)为根的子树的特征，则状态转移方程是（太♂难写已隐藏）。这样一遍\(\mathrm o(2^n)\)dfs则可求出所有节点的dp值。而我们希望找到所有节点为根时的根节点dp值，这个可以二次扫描与换根，即再一遍dfs。每到达一个节点\(x\)时，目前所有节点的dp值均是以\(x\)为整棵树的根的，所以若\(dp_x=(y,n)(y>0)\)，就将\(y\)加入答案序列。那么此时若要将它的某个儿子\(s\)改为根，那么改变的只有\(dp_x\)和\(dp_s\)。我们可以改一下它们的儿子集合（涉及添加和删除，用set较为方便），重新算dp值，然后再dfs到\(s\)，此时整棵树的根为\(s\)了。从\(s\)回溯时，再还原\(x\)和\(s\)的儿子集合和dp值，去找别的儿子即可。由于换根操作只需要改变\(2\)个节点的信息，所以复杂度是有保证的，一共\(\mathrm o(2^n\log_22^n)=\mathrm o(2^nn)\)（\(\log\)是set）。

下面贴代码：

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define x first
#define y second
const int n=17;
int n;
vector<int> nei[1<<n];/*邻接表*/ 
set<int> son[1<<n];/*儿子集合*/
void dfs(int x=1,int fa=0){//求出所有节点的儿子集合 
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa)continue;
        son[x].insert(y);
        dfs(y,x);
    }
}
pair<int,int> f[1<<n];//dp值，即以[1]为根的子树的特征 
void calc_f(int x){//通过儿子集合计算dp值，即那个难写的状态转移方程 
    if(son[x].size()==0)f[x]=mp(0,1);
    else if(son[x].size()==1)f[x]=f[*son[x].begin()]==mp(0,1)?mp(x,2):mp(-1,-1);
    else if(son[x].size()==2){
        pair<int,int> x1=f[*son[x].begin()],x2=f[*++son[x].begin()];
        if(x1>x2)swap(x1,x2);
        if(!x1.x&&!x2.x)f[x]=x1.y==x2.y?mp(0,x1.y+1):mp(-1,-1);
        else if(!x1.x&&x2.x>0)f[x]=x1.y==x2.y?mp(x2.x,x1.y+1):mp(-1,-1);
        else f[x]=mp(-1,-1);
    }
    else if(son[x].size()==3){
        pair<int,int> x1=f[*son[x].begin()],x2=f[*++son[x].begin()],x3=f[*++ ++son[x].begin()];
        if(x1>x2)swap(x1,x2);if(x2>x3)swap(x2,x3);if(x1>x2)swap(x1,x2);
        if(!x1.x&&!x2.x&&!x3.x)f[x]=x1.y==x2.y&&x2.y+1==x3.y?mp(x,x3.y+1):mp(-1,-1);
        else f[x]=mp(-1,-1);
    }
    else f[x]=mp(-1,-1);
//  printf("f[%d]=(%d,%d)\n",x,f[x].x,f[x].y);
}
void dp(int x=1,int fa=0){//一遍dfs求出以1为整棵树的根时的dp数组 
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa)continue;
        dp(y,x);
    }
    calc_f(x);
}
vector<int> ans;//答案序列 
void dfs0(int x=1,int fa=0){//二次扫描 
    if(f[x].x>0)ans.pb(f[x].x);//加入答案序列 
    for(int i=0;i<nei[x].size();i++){
        int y=nei[x][i];
        if(y==fa)continue;
        son[x].erase(y);son[y].insert(x);calc_f(x);calc_f(y);//改变儿子集合，重新算dp值 
        dfs0(y,x);
        son[x].insert(y);son[y].erase(x);calc_f(y);calc_f(x);//还原 
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=(1<<n)-3;i++){
        int x,y;
        cin>>x>>y;
        nei[x].pb(y);nei[y].pb(x);
    }
    dfs(); 
    dp();
    dfs0();
    cout<<ans.size()<<"\n";
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)cout<<ans[i]<<" ";
    return 0;
}