「清华集训 2017」小 Y 和二叉树

原题数据好像没有卡这个情况

1
2
3
4
5
6
5
1 2
2 1 3
3 2 4 5
1 3
1 3

输出是

1
1 2 3 4 5

首先考虑一个$O(n^2)$的暴力：

枚举一个点为根，向下展开树，此时只需要决策左儿子和右儿子的顺序

当两个子树都存在时，由于两个子树包含的元素不同，所以可以直接把 两个子树序列首较小 (显然不会出现相同的情况) 的一个放在前面即可

实际上我们可以发现，这样得到的序列第一个元素必然是 编号最小的 、不同时包含左右儿子 的结点

不妨称固定根之后，这样的结点为叶子

显然的性质：任何一个度数$\leq 2$的点可以作为答案序列的第一个点

设原树上最小的$\leq 2$的点为$root$，接下来对于$root$的不同情况讨论，要在强制$root$为序列首的情况下，求得最小的序列

不妨先预处理出结点$u$子树里最小的叶子$mi_u$

1.没有相邻结点，结束

2.有两个相邻结点，此时要使自己为序列首，必然有一个结点是自己的父亲，有一个结点是自己的右儿子

右儿子会被先遍历到，所以可以直接考虑比较两个相邻结点 作为 右儿子时谁的序列首 较小

即比较两个子树中最小的叶子即可

3.只有一个相邻结点，设其为$v$

此时要使得自己为序列第一个，只有两种可能，此时同样可以考虑比较序列首元素

3-1.让相邻结点作为自己的父亲，此时下一个元素一定是$v$

3-2.让相邻结点作为自己的右儿子，此时下一个元素一定是$mi_v$

如果$v\ne mi_v$，显然好决策

当$v=mi_v$时，必然满足$v$是一个叶子，此时如果将$v$放在父亲上，$v$的另一个相邻结点(如果存在)

可以放在$v$的父亲或者是$v$的右子树，如果放在$v$的右子树，那么这种情况与$v$被放在$u$的子树等价

也就是说，把$v$放在父亲可以决策出的序列情况，包含了把$v$放在右儿子的情况

所以这种情况也应当把$v$放在父亲上

实现上，不妨用两个$dfs$处理最后的决策，一个强制当前结点$u$为序列首，一个求出$u$子树的最优方案

在代码里就是$Solve,dfs_get$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;

#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }

char IO;
int rd(){
	int s=0,f=0;
	while(!isdigit(IO=getchar())) if(IO=='-') f=1;
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1e6+10;

int n;
int c[N],s[N][3];
int mi[N];

int rt=1e9;
void dfs(int u,int f) {
	mi[u]=1e9;
	int cnt=0;
	rep(i,0,c[u]-1) if(s[u][i]!=f) {
		int v=s[u][i]; cnt++;
		dfs(v,u),cmin(mi[u],mi[v]);
	}
	if(cnt<=1) cmin(mi[u],u);
}

int vis[N];
void dfs_get(int u) {
	vis[u]=1;
	int a=-1,b=-1;
	rep(i,0,c[u]-1) if(!vis[s[u][i]]) {
		int v=s[u][i];
		if(~a) b=v;
		else a=v;
	}
	if(a==-1) printf("%d ",u);
	else if(b==-1) {
		if(mi[a]<u) dfs_get(a),printf("%d ",u);
		else printf("%d ",u),dfs_get(a);
	} else {
		if(mi[a]>mi[b]) swap(a,b);
		dfs_get(a),printf("%d ",u),dfs_get(b);
	}
}

void Solve(int u) {
	int cnt=0;
	rep(i,0,c[u]-1) if(!vis[s[u][i]]) cnt++;
	vis[u]=1,printf("%d ",u);
	if(cnt==1) {
		rep(i,0,c[u]-1) if(!vis[s[u][i]]) {
			int v=s[u][i];
			if(v>mi[v]) dfs_get(s[u][i]);
			else Solve(v);
		}
	} else if(cnt==2) {
		int a=-1,b=-1;
		rep(i,0,c[u]-1) if(!vis[s[u][i]]) {
			int v=s[u][i];
			if(~a) b=v;
			else a=v;
		}
		if(mi[a]>mi[b]) swap(a,b);
		dfs_get(a),Solve(b);
	}
}

int main(){
	//freopen("binary.in","r",stdin),freopen("binary.out","w",stdout);
	n=rd();
	if(n==1) return puts("1"),0;
	rep(i,1,n) {
		c[i]=rd();
		if(c[i]<=2) cmin(rt,i);
		rep(j,0,c[i]-1) s[i][j]=rd();
	}
	dfs(rt,0);
	Solve(rt);
}