QOJ.ac

QOJ

ID提交记录ID题目HackerOwner结果提交时间测评时间
#542#334212#7222. The Great Huntricky_linricky_linFailed.2024-02-21 15:38:502024-02-21 15:38:51

详细

Extra Test:

Accepted
time: 695ms
memory: 16532kb

input:

9984
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
10 9
11 10
12 11
13 12
14 13
15 14
16 15
17 16
18 17
19 18
20 19
21 20
22 21
23 22
24 23
25 24
26 25
27 26
28 27
29 28
30 29
31 30
32 31
33 32
34 33
35 34
36 35
37 36
38 37
39 38
40 39
41 40
42 41
43 42
44 43
45 44
46 45
47 46
48 47
49 48
50 49
51 50
52 51
53 52
...

output:

No

result:

ok 

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#334212#7222. The Great Huntricky_linAC ✓264ms16808kbC++142.2kb2024-02-21 14:40:252024-02-21 14:40:26

answer

#include<bits/stdc++.h>
using namespace std;
const int NN = 1e4 + 8; 
int n;
inline int read(){
	register char c = getchar();
	register int res = 0;
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)) res = res * 10 + c - '0',c = getchar();
	return res;
}
struct Edge{
	int to,next;
}edge[NN << 1];
int head[NN],cnt;
void init(){
	memset(head,-1,sizeof(head));
	cnt = 1;
}
void add_edge(int u,int v){
	edge[++cnt] = {v,head[u]};
	head[u] = cnt;
}

int fa[NN],dep[NN];
void dfs(int u,int father){
	fa[u] = father;
	dep[u] = dep[father] + 1;
	for(int i = head[u]; i != -1; i = edge[i].next){
		int v = edge[i].to;
		if(v == father) continue;
		dfs(v,u);
	}
}

bitset<NN> e[NN];
int p[NN],rev[NN];
bitset<NN> vis;

//inline bool match(int u){
//	bitset<NN> now = e[u] & vis;
//	for(int v = now._Find_first(); v != NN; v = now._Find_next(v)){
//		vis.reset(v);
//		int x = p[v];
//		if(x){
//			if(match(x)){
//				p[v] = u;
//				return true;
//			}
//		}
//		else{
//			p[v] = u;
//			return true;
//		}
//	}
//	return false;
//} 递归版本 匈牙利 

int q[NN],prex[NN],prey[NN];
inline bool match(int s){
	int head,tail; 
	q[head = tail = 1] = s,vis.set();
	int res = 0;
	while(head <= tail){
		int u = q[head++];
		bitset<NN> now = e[u] & vis;
		for(int v = now._Find_first(); v != NN; v = now._Find_next(v)){
			vis.reset(v);
			int x = p[v];
			if(x) q[++tail] = x, prex[x] = u,prey[x] = v;
			else p[v] = res = u;
			if(res)break;
		}
		if(res)break;
	}
	if(!res) return false;
	for(int i = res; i != s; i = prex[i]) p[prey[i]] = prex[i];
	return true;
}//非递归版本 匈牙利 

int main(){
	n = read();
	init();
	for(int i = 1,u,v; i < n; ++i){
		u = read();v = read();
		add_edge(u,v);add_edge(v,u);
	}
	dfs(1,0);
	for(int i = 1,u,v; i <= n; ++i){
		u = read();v = read();
		if(dep[u] < dep[v]) swap(u,v);
		
		while(dep[u] > dep[v]) e[i].set(u),u = fa[u];
		while(u != v) e[i].set(u),e[i].set(v),u = fa[u],v = fa[v];
		e[i].set(u);
		vis.set();
		if(!match(i)){
			puts("No");
			return 0;
		}
	}
	
	puts("Yes");
	for(int i = 1; i <= n; ++i) rev[p[i]] = i;
	for(int i = 1; i <= n; ++i) printf("%d ",rev[i]);
}