CodeForces 1228F One Node is Gone
2019-10-16 07:50:17来源:博客园 阅读 ()
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出来。
我们将一个子树分类讨论:
- 是一棵满二叉树。设它的深度为\(d\),则记这颗子树的特征为有序对\((0,d)\)。这种情况发生当且仅当它有\(2\)棵子树并且都是矮\(1\)层的满二叉树。特殊地,如果它的大小为\(1\),则它的特征为\((0,1)\)。
还原一个节点之后为满二叉树。设还原之后的深度为\(d\),补的节点的父结点为\(x\),则记这棵子树的特征为有序对\((x,d)\)。这种情况发生当且仅当以下任意一个条件为真:
- 它的根为\(x\),有\(1\)棵子树并且这棵子树大小为\(1\),此时应将改补的节点直接补在\(x\)下。
- 它的根为\(x\),有\(3\)棵子树并且其中\(1\)棵为矮\(1\)层的满二叉树,另\(2\)棵为矮\(2\)层的满二叉树,此时应将改补的节点补在\(x\)下并将\(2\)棵矮\(2\)层的字树接在改补的节点下。
- 它有\(2\)棵子树并且一棵为矮\(1\)层的满二叉树,另一颗补一个父结点为\(x\)的节点之后为矮\(1\)层的满二叉树。
不管补不补节点都不能成为满二叉树。记它的特征为有序对\((-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;
}
原文链接:https://www.cnblogs.com/ycx-akioi/p/CodeForces-1228F.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
- CodeForces 1313D Happy New Year 2020-03-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash