QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731991#392. PatrolTheZone100 ✓110ms25928kbC++203.5kb2024-11-10 12:38:592024-11-10 12:39:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-10 12:39:02]
  • 评测
  • 测评结果：100
  • 用时：110ms
  • 内存：25928kb
查看
  • [2024-11-10 12:38:59]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>

using namespace std;

const int N = 100010;
const int INF = 0x3f3f3f3f;

int dep[N], n, k;
vector<int> E[N];
map<pair<int, int>, int> bin;
int fa[N], d1[N], d2[N];
void dfs(int u, int F) {
	fa[u] = F; dep[u] = dep[F] + 1;
	for (auto v : E[u]) if (v ^ F) dfs(v, u);
}
void dfs2(int u, int F) {
	for (auto v : E[u]) if (v ^ F) dfs2(v, u);
	for (auto v : E[u]) if (v ^ F) {
		if (d1[v] + bin[{u, v}] >= d1[u]) 
			d2[u] = d1[u], d1[u] = d1[v] + bin[{u, v}];
		else if (d1[v] + bin[{u, v}] > d2[u]) 
			d2[u] = d1[v] + bin[{u, v}];
	}
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i < n; i ++ ) {
		int a, b; scanf("%d%d", &a, &b);
		E[a].push_back(b), E[b].push_back(a);
		bin[{a, b}] = bin[{b, a}] = 1;
	} 
	if (k == 1) {
		dfs(1, 0);
		int root = max_element(dep + 1, dep + n + 1) - dep;
		memset(dep, 0, sizeof dep); dfs(root, 0);
		int d = *max_element(dep + 1, dep + n + 1) - 1;
		cout << (n - 1) * 2 - d + 1; return 0;
	} else {
		dfs(1, 0); 
		int root = max_element(dep + 1, dep + n + 1) - dep;
		memset(dep, 0, sizeof dep); memset(fa, 0, sizeof fa);
		dfs(root, 0); int z = max_element(dep + 1, dep + n + 1) - dep; 
		int D1 = dep[z] - 1; 
		while (z != root) bin[{z, fa[z]}] = bin[{fa[z], z}] = -1, z = fa[z];
		dfs2(root, 0); int D2 = -INF;
		for (int i = 1; i <= n; i ++ ) D2 = max(D2, d1[i] + d2[i]);
		cout << (n - 1) * 2 - D1 - D2 + 2 << endl;
	} return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 3.33333
Accepted
time: 1ms
memory: 6024kb

input:

10 1
2 1
3 1
4 1
5 2
6 5
7 1
8 2
9 2
10 9

output:

15

result:

ok single line: '15'

Test #2:

score: 3.33333
Accepted
time: 1ms
memory: 4076kb

input:

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

output:

385

result:

ok single line: '385'

Test #3:

score: 3.33333
Accepted
time: 0ms
memory: 4348kb

input:

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

output:

1831

result:

ok single line: '1831'

Test #4:

score: 3.33333
Accepted
time: 3ms
memory: 7008kb

input:

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

output:

9965

result:

ok single line: '9965'

Test #5:

score: 3.33333
Accepted
time: 9ms
memory: 7920kb

input:

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

output:

39961

result:

ok single line: '39961'

Test #6:

score: 3.33333
Accepted
time: 66ms
memory: 22876kb

input:

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

output:

199955

result:

ok single line: '199955'

Test #7:

score: 3.33333
Accepted
time: 5ms
memory: 7908kb

input:

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

output:

18340

result:

ok single line: '18340'

Test #8:

score: 3.33333
Accepted
time: 21ms
memory: 14500kb

input:

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

output:

91709

result:

ok single line: '91709'

Test #9:

score: 3.33333
Accepted
time: 52ms
memory: 23348kb

input:

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

output:

183360

result:

ok single line: '183360'

Test #10:

score: 3.33333
Accepted
time: 1ms
memory: 6428kb

input:

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

output:

28

result:

ok single line: '28'

Test #11:

score: 3.33333
Accepted
time: 1ms
memory: 6096kb

input:

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

output:

175

result:

ok single line: '175'

Test #12:

score: 3.33333
Accepted
time: 2ms
memory: 6764kb

input:

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

output:

1953

result:

ok single line: '1953'

Test #13:

score: 3.33333
Accepted
time: 9ms
memory: 7876kb

input:

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

output:

19934

result:

ok single line: '19934'

Test #14:

score: 3.33333
Accepted
time: 6ms
memory: 8376kb

input:

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

output:

19930

result:

ok single line: '19930'

Test #15:

score: 3.33333
Accepted
time: 42ms
memory: 14356kb

input:

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

output:

99922

result:

ok single line: '99922'

Test #16:

score: 3.33333
Accepted
time: 110ms
memory: 23412kb

input:

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

output:

199910

result:

ok single line: '199910'

Test #17:

score: 3.33333
Accepted
time: 0ms
memory: 4756kb

input:

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

output:

1798

result:

ok single line: '1798'

Test #18:

score: 3.33333
Accepted
time: 2ms
memory: 5060kb

input:

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

output:

3615

result:

ok single line: '3615'

Test #19:

score: 3.33333
Accepted
time: 8ms
memory: 6716kb

input:

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

output:

18240

result:

ok single line: '18240'

Test #20:

score: 3.33333
Accepted
time: 36ms
memory: 15736kb

input:

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

output:

91573

result:

ok single line: '91573'

Test #21:

score: 3.33333
Accepted
time: 42ms
memory: 21876kb

input:

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

output:

146479

result:

ok single line: '146479'

Test #22:

score: 3.33333
Accepted
time: 58ms
memory: 25928kb

input:

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

output:

183232

result:

ok single line: '183232'

Test #23:

score: 3.33333
Accepted
time: 3ms
memory: 7756kb

input:

10000 2
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 5
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 33
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 5...

output:

19495

result:

ok single line: '19495'

Test #24:

score: 3.33333
Accepted
time: 6ms
memory: 8520kb

input:

10000 2
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 ...

output:

18913

result:

ok single line: '18913'

Test #25:

score: 3.33333
Accepted
time: 31ms
memory: 14128kb

input:

50000 2
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 ...

output:

98142

result:

ok single line: '98142'

Test #26:

score: 3.33333
Accepted
time: 33ms
memory: 13828kb

input:

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

output:

99957

result:

ok single line: '99957'

Test #27:

score: 3.33333
Accepted
time: 37ms
memory: 13868kb

input:

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

output:

99970

result:

ok single line: '99970'

Test #28:

score: 3.33333
Accepted
time: 59ms
memory: 22932kb

input:

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

output:

199971

result:

ok single line: '199971'

Test #29:

score: 3.33333
Accepted
time: 80ms
memory: 23344kb

input:

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

output:

199949

result:

ok single line: '199949'

Test #30:

score: 3.33333
Accepted
time: 80ms
memory: 23068kb

input:

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

output:

199976

result:

ok single line: '199976'
English 繁體中文 简体中文

Server Time: 2024-12-04 06:19:12 | OpenSource Project