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

Posted on Edited on In

「清华集训 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);
}