Codeforces 1228F One Node is Gone 题解
题意
给定$n (1\le n\le17)$,定义McDic’s generation为
- 建一个有$2^n-1$个结点的满二叉树
- 从这个二叉树中选择一个非根结点$v$
- 把$v$从树中删除,从$v$的父亲到$v$的儿子连边,如果$v$没有儿子,那么就不连边。
现在给定一棵树,判断这棵树是否可以经过McDic’s generation一次得到。如果可以,输出被删除的结点的父亲。
题解
首先,要找到这棵树的根。我们知道,一棵满二叉树的根结点在它的直径的中间,而删除一个结点后,根在直径的位置可能会偏移$1$个,为了保险,可以假设它偏移了$2$个位置。把这$5$个结点当作根,进行DFS
。
设当前点为$x$,$cnt$为$x$的儿子个数,DFS(x)
的返回值为一个pair<int,int>
,其中:
- 如果以$x$为根的子树非法,返回
{0,-1}
- 如果以$x$为根的子树为一个满二叉树,返回
{1,x离叶子结点的距离}
- 如果被删除的结点在以$x$为根的子树内,返回
{2,x离叶子结点的距离}
很容易知道,如果cnt>3
,则返回{0,-1}
;如果cnt=0
,则它是叶子结点,返回{1,0}
。
如果$x$不为以上两种情况,DFS
它的儿子$y$,设DFS(y)
的返回值为$got$
如果
got.first=0
,则以$x$为根的子树也非法,返回{0,-1}
如果
got.first=1
,则把got.second
存入vector<int> valid
如果
got.first=2
,则把got.second
存入vector<int> spec
如果spec.size()>=2
,显然非法,返回{0,-1}
对valid
排序。
如果cnt=1
,说明被删除的结点是它的叶子结点,
- 如果
valid.size()=1且valid[0]=0
,合法,存储答案并返回{2,1}
- 否则返回
{0,-1}
如果cnt=2
,
如果
valid.size()=2且valid[0]=valid[1]
,说明它是一个正常的满二叉树,返回{1,valid[0]+1}
如果
valid.size()=1且valid[0]=spec[0]
,说明被删除的结点在它的其中一个子树中,返回{2,valid[0]+1}
否则返回
{0,-1}
如果cnt=3
,
如果
valid.size()=3且valid[0]=valid[1]且valid[1]+1=valid[2]
,说明它的其中一个儿子被删除了,返回{2,valid[2]+1}
否则返回
{0,-1}
程序
1 | // #pragma GCC optimize(2) |