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\)的節點之后為矮\(1\)層的滿二叉樹；

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\log2^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;
}

標籤：C++

上一篇：CodeForces 309B - Context Advertising

下一篇：數位的處理