CF29D 题解

发表于
自己想出来的构造题

翻了一下题解区，似乎没有跟我一样的做法？这里提供一种不用 LCA，复杂度同样为 $O(n\log n)$ 的做法。

解题思路

因为我们对叶子节点的遍历顺序有一定要求，我们考虑要走到叶子节点一定会走到他的所有祖先。

于是我们可以 DFS 一遍整棵树，给每个节点一个优先级。叶子节点的优先级就是遍历到他的顺序，其他节点的优先级则是它子树内所有叶节点优先级的最小值。特别地，对于没有规定遍历顺序的叶子结点，我们可以直接把它的优先级设为 $n$。

然后我们再 DFS 一遍，这次 DFS 的顺序就是我们要的答案。DFS 的过程中遵循两个原则：

  1. 一旦遍历到某个节点，就要把该节点的子树遍历完。

  2. 每次按优先级的顺序遍历一个节点的儿子。

在 DFS 的同时，我们记录一下当前经过叶节点的序是否与题目要求相符，不相符则说明无解。

丑陋的代码

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,cnt,lst[305],xu[305],tmp,now=1,wt[305];
struct edge{
	int f,t,lst;
	edge(int f=0,int t=0,int lst=0):
		f(f),t(t),lst(lst){};
}e[605];
void add(int u,int v){
	e[++cnt]=edge(u,v,lst[u]);lst[u]=cnt;
	e[++cnt]=edge(v,u,lst[v]);lst[v]=cnt;
}
int dfs(int u,int f){
	int ret=n+1;
	if(xu[u])ret=xu[u];
	for(int i=lst[u];i;i=e[i].lst){
		int v=e[i].t;
		if(v==f)continue;
		ret=min(ret,dfs(v,u));
	}
	wt[u]=ret;
	return ret;
}
vector<int> ans;
struct node{
	int id;
	bool operator<(node b)const{
		return wt[id]<wt[b.id];
	}
};
bool dfs2(int u,int f){
	ans.push_back(u);
	if(xu[u]&&xu[u]!=now)return 0;
	if(xu[u])now++;
	vector<node> son;
	for(int i=lst[u];i;i=e[i].lst){
		int v=e[i].t;
		if(v==f)continue;
		son.push_back((node){v});
	}
	sort(son.begin(),son.end());
	bool ret=1;
	for(int i=0;i<son.size();i++){
		ret&=dfs2(son[i].id,u);
		ans.push_back(u);
	}
	return ret;
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	int now;
	while(cin>>now){
		xu[now]=++tmp;
	}
	dfs(1,0);
	if(!dfs2(1,0))puts("-1");
	else{
		for(int i=0;i<ans.size();i++)cout<<ans[i]<<' ';
	}
	return 0;
}