UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#213649#2769. 覆盖STASISZHY01833ms400216kbC++112.3kb2024-11-12 22:39:232024-11-13 00:05:24

answer

// Problem: C. 覆盖
// Contest: undefined - NOIP2024训练赛 03
// URL: http://119.28.3.174/contest/1155/problem/2769
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
//#define int long long
#define fi first   
#define se second
#define PII pair<int, int>

using namespace std;

const int N = 2e6 + 10, M = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;

int n, m, q, ans, ti;
int dp[N], dep[N], f[N][35], sum[N], dfn[N];

// map<PII, int> id;
struct node
{
	int lca, x, y;
}s[N];

inline bool cmp(node a, node b) {return dep[a.lca] > dep[b.lca];}

vector<int> e[N], v;

void dfs(int now, int fa)
{
  	dep[now] = dep[fa] + 1, f[now][0] = fa, dfn[now] = ++ ti;
  	for(auto i : e[now]) if(i != fa) dfs(i, now);
}

inline int lca(int x, int y)
{
  	if(dep[x] < dep[y]) swap(x, y);
  	for(int i = 30; ~ i; i --) if(dep[f[x][i]] >= dep[y]) x = f[x][i];
  	  	// cout << "x = " << x << " y = " << y << '\n';
  	if(x == y) return x;
  	for(int i = 30; ~ i; i --) if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
  	return f[x][0];
}

inline bool check(int i, int now)
{
	// cout << "lst = " << i << " lca = " << s[now].lca << '\n'; 
	if(lca(i, s[now].lca) == s[now].lca && lca(i, s[now].x) == i) return true;
	if(lca(i, s[now].lca) == s[now].lca && lca(i, s[now].y) == i) return true;
	return false;
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i < n; i ++)
	{
		int u, v; cin >> u >> v;
		e[u].push_back(v), e[v].push_back(u);
	}	
	dfs(1, 0);
	// for(int i = 1; i <= n; i ++) cout << dfn[i] << ' ';
	// cout << '\n';
	for(int j = 1; j <= 30; j ++)
 	 	for(int i = 1; i <= n; i ++) f[i][j] = f[f[i][j - 1]][j - 1];
	cin >> q;
	for(int i = 1; i <= q; i ++) 
	{
		int x, y; cin >> x >> y;
		s[i] = {lca(x, y), x, y};
	}
	sort(s + 1, s + q + 1, cmp);
	// cout << s[1].lca << '\n';
	// cout << lca(10, 8) << '\n';
	int lst = s[1].lca; v.push_back(s[1].lca);
	for(int i = 2; i <= q; i ++)
	{
		if(check(lst, i)) continue;
		// cout << s[i].x << ' ' << s[i].y << '\n';
		v.push_back(s[i].lca), lst = s[i].lca;
	}
	cout << v.size() << '\n';
	sort(v.begin(), v.end());
	for(auto i : v) cout << i << ' ';
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 30
Accepted
time: 11ms
memory: 48164kb

input:

20
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 13
17 15
18 16
19 17
20 18
...

output:

2
3 10 

result:

ok ok

Test #2:

score: 0
Accepted
time: 4ms
memory: 48160kb

input:

20
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
...

output:

2
6 13 

result:

ok ok

Test #3:

score: 0
Accepted
time: 4ms
memory: 48168kb

input:

20
2 1
3 1
4 3
5 1
6 5
7 4
8 7
9 8
10 9
11 10
12 6
13 2
14 7
15 14
16 11
17 12
18 17
19 7
20 15
5
4 ...

output:

3
1 4 11 

result:

ok ok

Test #4:

score: 0
Accepted
time: 3ms
memory: 48160kb

input:

20
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
...

output:

2
5 11 

result:

ok ok

Test #5:

score: 0
Accepted
time: 7ms
memory: 48164kb

input:

20
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 6
10 8
11 10
12 11
13 11
14 12
15 13
16 9
17 15
18 16
19 16
20 17
1...

output:

6
1 3 7 10 17 19 

result:

ok ok

Test #6:

score: -30
Wrong Answer
time: 4ms
memory: 48164kb

input:

20
2 1
3 2
4 3
5 3
6 5
7 4
8 6
9 8
10 7
11 7
12 10
13 12
14 13
15 9
16 14
17 16
18 16
19 17
20 15
12...

output:

4
2 4 9 13 

result:

wrong answer Arrangement not optimal

Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 0
Wrong Answer
time: 4ms
memory: 48336kb

input:

1000
2 1
3 2
4 3
5 4
6 3
7 6
8 7
9 8
10 9
11 10
12 5
13 11
14 13
15 14
16 15
17 12
18 16
19 18
20 19...

output:

24
3 5 23 53 78 80 98 101 110 131 182 186 206 235 250 261 275 280 289 317 397 407 471 585 

result:

wrong answer Arrangement not optimal

Subtask #3:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 1796ms
memory: 400216kb

input:

2000000
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 11
15 14
16 13
17 15
18 16
19 17
2...

output:

6
260 10715 16698 19031 23494 49620 

result:

wrong answer Arrangement not optimal