QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#787218#9751. 覆盖一棵树fatesrl#AC ✓35ms35860kbC++201.2kb2024-11-27 10:26:182024-11-27 10:26:18

Judging History

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

  • [2024-11-27 10:26:18]
  • 评测
  • 测评结果:AC
  • 用时:35ms
  • 内存:35860kb
  • [2024-11-27 10:26:18]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
vector mp(0,vector (0,0));
vector deep(0,0);
vector dpt(0,0);
typedef pair<int,int> pii;
int mxd=0;
vector mpt(0,vector (0,0));
void dfs(int d,int fa){
	for(auto x:mp[d]){
		if(x==fa) continue;
		deep[x]=deep[d]+1;
		if(deep[x]>deep[mxd]) mxd=x;
		dfs(x,d);
	}
}
void solve(){
	int n;
	cin>>n;
	mp.assign(n+1,vector<int>(0));
	mpt.assign(n+1,vector<int>(0));
	for(int i=2;i<=n;i++){
		int x;
		cin>>x;
		mp[x].push_back(i);
		mpt[i].push_back(x);
	}
	mxd=1;
	deep.assign(n+1,0);
	deep[1]=0;
	dfs(1,0);
//	cout<<1<<'\n';
	vector<pii> ins;
	for(int i=1;i<=n;i++) if(mp[i].size()==0) ins.push_back({deep[i],i});
	sort(ins.begin(),ins.end());
	dpt.assign(n+1,0);
	int ans=0;
	for(auto [x,y]:ins){
		int cnt=0;
//		cout<<y<<' ';
		while(1){
//			cout<<y<<'\n';
			dpt[y]=1;
			cnt++;
//			if(mpt[y].size()==0) break;
			y=mpt[y][0];
			if(dpt[y]||mpt[y].size()==0){
				cnt++;
				break;
			}
		} 
//		cout<<' '<<cnt<<'\n';
		ans=max(ans,cnt-1);
	}
	cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int ins=1;
	cin>>ins;
	while(ins--) solve();
	return 0;
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

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

output:

3
7

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 12ms
memory: 3544kb

input:

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

output:

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

result:

ok 33428 lines

Test #3:

score: 0
Accepted
time: 15ms
memory: 3620kb

input:

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

output:

11
20
24
28
10
23
5
31
8
19
7
14
1
15
14
14
15
9
11
10
11
13
5
31
23
9
11
23
32
18
17
18
10
14
1
24
1
28
18
13
9
10
9
12
24
5
27
27
9
29
15
17
23
20
17
11
14
12
19
9
19
13
17
16
14
7
17
23
5
20
11
14
8
9
18
2
9
16
29
17
2
31
13
14
3
16
9
26
14
15
13
5
17
18
19
24
12
20
10
10
13
14
13
2
12
10
15
18
1...

result:

ok 3934 lines

Test #4:

score: 0
Accepted
time: 12ms
memory: 3792kb

input:

386
208
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

27
31
36
29
27
27
23
31
27
30
25
28
37
14
27
23
35
30
32
52
38
58
31
34
28
43
37
39
32
33
22
34
28
27
39
25
25
45
32
23
25
47
24
48
28
34
45
22
26
37
13
32
32
24
40
22
26
33
23
25
31
21
19
45
9
24
23
27
27
32
40
15
22
33
21
44
36
29
24
28
44
43
23
43
31
19
36
33
50
22
18
20
9
41
34
58
22
25
21
18
34...

result:

ok 386 lines

Test #5:

score: 0
Accepted
time: 16ms
memory: 5268kb

input:

42
8830
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

65
52
46
34
42
48
35
40
40
43
42
46
44
44
52
39
54
37
43
29
40
38
45
43
51
48
35
37
56
48
47
37
30
42
42
32
43
56
53
53
48
37

result:

ok 42 lines

Test #6:

score: 0
Accepted
time: 27ms
memory: 17988kb

input:

5
51400
1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

65
58
58
37
57

result:

ok 5 lines

Test #7:

score: 0
Accepted
time: 25ms
memory: 26400kb

input:

2
56002
1 2 3 3 4 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 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 70 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

119
105

result:

ok 2 lines

Test #8:

score: 0
Accepted
time: 26ms
memory: 26976kb

input:

2
56002
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

56001
143997

result:

ok 2 lines

Test #9:

score: 0
Accepted
time: 35ms
memory: 24596kb

input:

1
200000
1 2 2 4 4 6 7 8 8 8 11 12 8 7 7 7 17 6 19 19 6 4 4 24 25 25 27 27 29 24 31 31 31 34 4 36 36 2 39 40 39 39 43 44 45 46 47 48 47 47 51 52 45 54 45 56 57 56 59 45 61 62 61 64 64 66 45 68 69 69 71 71 73 73 69 76 77 78 78 68 68 82 68 45 85 85 87 85 89 90 91 91 90 94 94 90 89 98 98 100 101 102 98...

output:

8

result:

ok single line: '8'

Test #10:

score: 0
Accepted
time: 20ms
memory: 22928kb

input:

1
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39...

output:

2

result:

ok single line: '2'

Test #11:

score: 0
Accepted
time: 35ms
memory: 25284kb

input:

1
200000
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

output:

247

result:

ok single line: '247'

Test #12:

score: 0
Accepted
time: 34ms
memory: 22992kb

input:

1
200000
1 1 1 1 1 1 1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 1 133 133 133 133 133 133 133...

output:

2

result:

ok single line: '2'

Test #13:

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

input:

1
200000
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

output:

161

result:

ok single line: '161'

Test #14:

score: 0
Accepted
time: 25ms
memory: 15236kb

input:

2
100000
1 2 3 4 3 6 3 3 9 3 11 12 13 3 15 15 15 2 19 2 2 2 1 24 25 26 27 28 29 30 30 29 27 27 35 36 37 38 27 27 41 42 42 26 45 46 47 47 49 50 51 46 53 53 46 56 46 58 58 60 61 61 63 60 65 65 60 68 58 70 70 72 70 74 74 76 74 78 79 79 78 82 78 84 78 74 87 88 89 90 74 74 93 58 46 96 97 98 98 98 101 102...

output:

7
7

result:

ok 2 lines

Test #15:

score: 0
Accepted
time: 16ms
memory: 3616kb

input:

100000
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2
1
2...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
...

result:

ok 100000 lines

Test #16:

score: 0
Accepted
time: 15ms
memory: 22600kb

input:

1
200000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...

output:

1

result:

ok single line: '1'

Test #17:

score: 0
Accepted
time: 25ms
memory: 35860kb

input:

1
200000
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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...

output:

199999

result:

ok single line: '199999'

Extra Test:

score: 0
Extra Test Passed