UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#213523#2769. 覆盖nodgd10031378ms257624kbC++112.2kb2024-11-12 19:47:312024-11-12 23:20:03

answer

#include <bits/stdc++.h>

using namespace std;

namespace FastRead{
	char buf[1000005], *s = buf, *t = buf, ch, f;
	#define gc() s == t && (t = (s = buf) + fread(buf, 1, 1000000, stdin), s == t) ? EOF : *s ++ 
	template <typename T>
	inline void Read(T &x)
	{
		x = f = 0, ch = gc();
		while(ch < '0' || ch > '9')
		{
			if(ch == '-') f = 1;
			ch = gc();
		}
		while('0' <= ch && ch <= '9') x = x * 10 + ch - 48, ch = gc();
		f && (x = -x);
	}
};
using FastRead::Read;

const int N = 2e6 + 5, K = 22;

int n, m;
int la[N], ne[N * 2], en[N * 2], idx;
int fa[N][K], dep[N], in[N], out[N], dfst;
struct Node{
	int u, v, w, d;
	bool operator <(const Node &w) const
	{
		return d > w.d;
	}
}x[N];
int cnt, vis[N], c[N];

inline void Add(int a, int b)
{
	ne[ ++ idx] = la[a];
	la[a] = idx;
	en[idx] = b;
}
inline void DFS(int u, int f)
{
	fa[u][0] = f, dep[u] = dep[f] + 1;
	for(int i = 1; i < K; i ++ ) fa[u][i] = fa[fa[u][i - 1]][i - 1];
	in[u] = ++ dfst;
	for(int i = la[u]; i; i = ne[i])
	{
		int v = en[i];
		if(v != f) DFS(v, u);
	}
	out[u] = dfst;
}
inline int LCA(int u, int v)
{
	if(dep[u] < dep[v]) swap(u, v);
	for(int i = K - 1; i >= 0; i -- )
		if(dep[fa[u][i]] >= dep[v])
			u = fa[u][i];
	if(u == v) return u;
	for(int i = K - 1; i >= 0; i -- )
		if(fa[u][i] != fa[v][i])
			u = fa[u][i], v = fa[v][i];
	return fa[u][0];
}

inline void Modify(int i, int d)
{
	for(; i <= n; i += i & -i) c[i] += d;
}
inline int Sum(int i)
{
	int s = 0;
	for(; i; i &= i - 1) s += c[i];
	return s;
}

int main()
{
	Read(n);
	for(int i = 1; i < n; i ++ )
	{
		int a, b;
		Read(a), Read(b);
		Add(a, b), Add(b, a);
	}
	DFS(1, 0);

    Read(m);
	for(int i = 1; i <= m; i ++ )
	{
		Read(x[i].u), Read(x[i].v);
		x[i].w = LCA(x[i].u, x[i].v);
		x[i].d = dep[x[i].w];
	}
	sort(x + 1, x + m + 1);
	for(int i = 1; i <= m; i ++ )
	{
//		printf("*%d %d %d\n", x[i].u, x[i].v, x[i].w);
		if(Sum(in[x[i].u]) + Sum(in[x[i].v]) - Sum(in[x[i].w]) - Sum(in[fa[x[i].w][0]]) == 0)
		{
			vis[x[i].w] = 1;
			cnt ++ ;
			Modify(in[x[i].w], 1);
			Modify(out[x[i].w] + 1, -1);
		}
	}
	printf("%d\n", cnt);
	for(int i = 1; i <= n; i ++ ) if(vis[i]) printf("%d ", i);
	puts("");
	return 0;
}

详细

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

Subtask #1:

score: 30
Accepted

Test #1:

score: 30
Accepted
time: 0ms
memory: 1208kb

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: 0ms
memory: 1204kb

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: 0ms
memory: 1204kb

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: 0ms
memory: 1204kb

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: 0ms
memory: 1208kb

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: 0
Accepted
time: 0ms
memory: 1208kb

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:

3
4 9 13 

result:

ok ok

Test #7:

score: 0
Accepted
time: 0ms
memory: 1192kb

input:

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

output:

2
5 8 

result:

ok ok

Test #8:

score: 0
Accepted
time: 0ms
memory: 1208kb

input:

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

output:

2
4 10 

result:

ok ok

Test #9:

score: 0
Accepted
time: 0ms
memory: 1208kb

input:

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

output:

3
3 8 10 

result:

ok ok

Test #10:

score: 0
Accepted
time: 0ms
memory: 1204kb

input:

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

output:

2
7 12 

result:

ok ok

Subtask #2:

score: 30
Accepted

Test #11:

score: 30
Accepted
time: 0ms
memory: 1336kb

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:

11
53 131 186 235 258 280 289 317 397 471 585 

result:

ok ok

Test #12:

score: 0
Accepted
time: 0ms
memory: 1340kb

input:

1000
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 12
16 14
17 16
18 17
19 18
20 1...

output:

16
96 109 110 114 152 154 179 285 315 418 463 469 526 561 610 822 

result:

ok ok

Test #13:

score: 0
Accepted
time: 1ms
memory: 1336kb

input:

1000
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 1...

output:

2
40 305 

result:

ok ok

Test #14:

score: 0
Accepted
time: 0ms
memory: 1340kb

input:

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

output:

15
36 77 111 161 164 218 236 277 281 391 408 410 460 577 738 

result:

ok ok

Test #15:

score: 0
Accepted
time: 0ms
memory: 1344kb

input:

1000
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 1...

output:

17
46 104 126 230 293 313 324 439 460 462 469 504 513 526 546 646 694 

result:

ok ok

Test #16:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

1000
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 1...

output:

6
18 114 168 201 311 651 

result:

ok ok

Test #17:

score: 0
Accepted
time: 0ms
memory: 1340kb

input:

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

output:

16
11 42 68 113 171 249 311 341 361 373 423 450 497 567 586 649 

result:

ok ok

Test #18:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

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

output:

4
15 167 387 437 

result:

ok ok

Test #19:

score: 0
Accepted
time: 0ms
memory: 1336kb

input:

1000
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 1...

output:

10
33 158 210 236 363 364 367 372 873 978 

result:

ok ok

Test #20:

score: 0
Accepted
time: 0ms
memory: 1332kb

input:

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

output:

5
7 85 118 241 307 

result:

ok ok

Subtask #3:

score: 40
Accepted

Test #21:

score: 40
Accepted
time: 849ms
memory: 237012kb

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:

5
260 10715 16698 23494 49620 

result:

ok ok

Test #22:

score: 0
Accepted
time: 950ms
memory: 238048kb

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

output:

45
2404 7524 11229 11999 14383 16080 18852 24573 25801 31547 35420 37754 42334 58888 69242 72415 820...

result:

ok ok

Test #23:

score: 0
Accepted
time: 1013ms
memory: 243352kb

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

output:

288
553 5636 9673 9795 15417 22482 28415 29113 30841 31695 36154 36370 41110 45282 46034 47993 48884...

result:

ok ok

Test #24:

score: 0
Accepted
time: 1187ms
memory: 241120kb

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

output:

172
4997 8750 17928 18489 27327 30718 32013 33965 34115 42664 44246 55789 56336 56495 57194 69263 74...

result:

ok ok

Test #25:

score: 0
Accepted
time: 1625ms
memory: 250712kb

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

output:

635
969 1796 5534 7302 8367 9149 10058 10082 10729 13481 14831 15038 17852 18658 20221 22753 25477 2...

result:

ok ok

Test #26:

score: 0
Accepted
time: 1043ms
memory: 237768kb

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

output:

27
5198 7509 8142 27608 34761 38220 48041 50127 56909 61117 71286 81891 86675 104143 114045 119648 1...

result:

ok ok

Test #27:

score: 0
Accepted
time: 835ms
memory: 237012kb

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

output:

6
490 3177 5695 8562 34548 83430 

result:

ok ok

Test #28:

score: 0
Accepted
time: 1024ms
memory: 241908kb

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

output:

220
1404 2780 5137 10384 13852 18479 22969 35367 37404 38380 41605 44793 46628 49267 50316 54862 579...

result:

ok ok

Test #29:

score: 0
Accepted
time: 857ms
memory: 237448kb

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

output:

18
2171 9580 14974 16009 28264 35966 39104 40324 45067 52501 56381 68915 76116 77646 77795 181356 21...

result:

ok ok

Test #30:

score: 0
Accepted
time: 949ms
memory: 238148kb

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

output:

45
2737 4251 12786 13429 14598 22080 22736 22786 25916 26716 30601 38898 40197 45646 47158 61559 631...

result:

ok ok

Test #31:

score: 0
Accepted
time: 1125ms
memory: 237864kb

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

output:

32
1116 16424 21197 23111 23813 27073 27779 32582 47061 49460 49619 54106 60014 60225 61690 63492 67...

result:

ok ok

Test #32:

score: 0
Accepted
time: 1140ms
memory: 237088kb

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

output:

5
5384 6708 15117 19941 80900 

result:

ok ok

Test #33:

score: 0
Accepted
time: 828ms
memory: 237204kb

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

output:

11
4421 6325 8344 16347 35897 44930 46860 57419 78545 299866 326571 

result:

ok ok

Test #34:

score: 0
Accepted
time: 856ms
memory: 236864kb

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

output:

2
5187 7452 

result:

ok ok

Test #35:

score: 0
Accepted
time: 933ms
memory: 241512kb

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

output:

192
800 3704 4872 12578 14477 19995 22579 25124 29417 31207 32243 34402 42016 44099 44679 45783 4791...

result:

ok ok

Test #36:

score: 0
Accepted
time: 1343ms
memory: 247396kb

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

output:

489
39 5656 7050 7487 10829 12376 13186 13483 24437 27366 29300 31447 37089 37325 41271 41767 45145 ...

result:

ok ok

Test #37:

score: 0
Accepted
time: 857ms
memory: 236896kb

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

output:

2
1572 10047 

result:

ok ok

Test #38:

score: 0
Accepted
time: 853ms
memory: 237136kb

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

output:

6
5177 16799 17244 21899 124227 342086 

result:

ok ok

Test #39:

score: 0
Accepted
time: 826ms
memory: 237052kb

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

output:

3
9574 37101 114239 

result:

ok ok

Test #40:

score: 0
Accepted
time: 1184ms
memory: 246340kb

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

output:

434
2752 3375 3689 4991 6053 9618 12539 12689 13788 16278 19244 20277 22749 25323 28033 30314 36310 ...

result:

ok ok

Test #41:

score: 0
Accepted
time: 856ms
memory: 236956kb

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

output:

3
4025 12701 18588 

result:

ok ok

Test #42:

score: 0
Accepted
time: 984ms
memory: 238168kb

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

output:

46
1396 4100 10862 12634 18427 21454 23016 23231 23273 30104 38220 53924 55565 63057 75176 78809 795...

result:

ok ok

Test #43:

score: 0
Accepted
time: 835ms
memory: 237228kb

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

output:

9
7458 12356 16676 19276 29074 30431 45809 48149 71934 

result:

ok ok

Test #44:

score: 0
Accepted
time: 873ms
memory: 237540kb

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

output:

21
3775 7530 8870 10517 18085 30025 34965 42583 58317 58508 59568 71429 100130 147513 149176 154795 ...

result:

ok ok

Test #45:

score: 0
Accepted
time: 2220ms
memory: 257624kb

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

output:

902
1097 2377 2384 2850 4587 8343 10511 12075 12386 12906 14030 14419 14466 16460 17707 21340 21375 ...

result:

ok ok

Test #46:

score: 0
Accepted
time: 850ms
memory: 236872kb

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

output:

1
8442 

result:

ok ok

Test #47:

score: 0
Accepted
time: 839ms
memory: 237168kb

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

output:

9
5252 6422 19409 22535 24115 36225 56798 215617 409005 

result:

ok ok

Test #48:

score: 0
Accepted
time: 852ms
memory: 237004kb

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

output:

5
428 7180 7718 16350 48522 

result:

ok ok

Test #49:

score: 0
Accepted
time: 1230ms
memory: 236892kb

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

output:

2
1290 14389 

result:

ok ok

Test #50:

score: 0
Accepted
time: 1561ms
memory: 248964kb

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

output:

559
945 1241 5644 8082 9005 9959 10848 12448 12793 14252 20587 20906 23833 27004 27886 28406 29166 3...

result:

ok ok

Extra Test:

score: 0
Extra Test Passed