QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#632385#5124. TreeGreen_Hand#AC ✓21ms17152kbC++201023b2024-10-12 13:18:352024-10-12 13:18:40

Judging History

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

  • [2024-10-12 13:18:40]
  • 评测
  • 测评结果:AC
  • 用时:21ms
  • 内存:17152kb
  • [2024-10-12 13:18:35]
  • 提交

answer

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 1E6 + 7;
int n,l,r,ans,now,T,id[N],q[N],D[N],fa[N];

int min(int x,int y) { return x < y ? x : y; }

int max(int x,int y) { return x > y ? x : y; }

void read(int &x)
{
	char c = getchar(); x = 0;
	while(c < '0' || c > '9') c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}

int main()
{
	for(read(T);T--;)
	{
		read(n);
		for(int i = 1;i <= n; ++ i) D[i] = 0;
		for(int i = 2;i <= n; ++ i) read(fa[i]), ++D[fa[i]];
		
		now = l = 1, r = 0;
		for(int i = 1;i <= n; ++ i)
			!D[i] && (q[++r] = i, id[i] = 1) || (now += D[i] - 1);
		ans = now;
		
		for(int i = 1;l <= r; ++ i)
		{
			for(int x;l <= r && id[x = q[l]] == i; ++ l)
			{
				now -= max(0,D[fa[x]] - 1);
				if(x == 1) { ans = min(ans,i); continue; }
				if(!--D[fa[x]]) id[fa[x]] = i + 1, q[++r] = fa[x];
				else now += D[fa[x]] - 1;
			}
			ans = min(ans,now + i);
		}
		printf("%d\n",ans);
	}
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7644kb

input:

2
7
1 1 2 2 2 3
5
1 2 3 4

output:

3
1

result:

ok 2 number(s): "3 1"

Test #2:

score: 0
Accepted
time: 8ms
memory: 7616kb

input:

46234
1

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

output:

1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
3
2
2
2
3
2
3
3
3
3
2
2
2
3
3
2
3
3
3
2
2
2
3
3
3
2
3
3
2
2
2
3
3
3
3
2
3
2
2
2
3
3
3
3
3
2
2
2
2
2
2
3
3
3
3
2
3
2
2
2
3
3
3
3
2
2
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
2
2
2
3
3
3
3
2
2
2
2
2
3
2
3
3
3
2
3
3
3
3
3
3
3
...

result:

ok 46234 numbers

Test #3:

score: 0
Accepted
time: 19ms
memory: 17096kb

input:

1
1000000
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 10...

output:

1

result:

ok 1 number(s): "1"

Test #4:

score: 0
Accepted
time: 13ms
memory: 17140kb

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:

1000

result:

ok 1 number(s): "1000"

Test #6:

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

input:

1
1000000
1 1 1 2 3 4 5 6 7 3 6 8 9 10 13 11 12 13 14 15 8 16 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 51 39 54 55 56 57 58 59 60 61 68 62 63 64 65 66 67 68 69 70 71 59 72 73 74 75 76 77 78 79 80 81 82 32 23 83 84 85 86 87 88 8...

output:

1405

result:

ok 1 number(s): "1405"

Test #7:

score: 0
Accepted
time: 21ms
memory: 17120kb

input:

1
1000000
1 1 1 1 2 3 4 5 6 7 8 9 10 11 14 1 12 13 14 15 19 16 17 18 19 20 21 20 22 23 24 25 26 27 28 20 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 29 46 47 48 49 50 51 52 53 54 53 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 51 76 77 78 79 80 81 82 83 84 85 86 23 87 88 89 ...

output:

1404

result:

ok 1 number(s): "1404"

Test #8:

score: 0
Accepted
time: 18ms
memory: 17152kb

input:

1
1000000
1 1 1 2 4 3 4 5 6 7 8 9 10 5 10 11 12 13 11 17 14 15 16 17 18 19 20 21 22 23 24 25 26 27 14 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 16 45 46 47 48 49 50 51 52 53 17 54 55 56 57 58 59 60 61 62 63 40 67 64 65 66 67 68 69 70 71 72 73 74 54 35 75 76 77 78 79 80 81 82 83 84 85 86 87 ...

output:

1406

result:

ok 1 number(s): "1406"

Test #9:

score: 0
Accepted
time: 17ms
memory: 8232kb

input:

7
142857
1 1 2 1 2 3 4 4 8 5 6 7 8 9 10 11 12 13 14 7 15 15 16 17 18 19 20 21 22 23 24 25 26 27 28 17 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 14 55 56 57 58 59 60 61 62 63 27 69 43 64 65 66 67 68 69 70 71 72 73 57 15 74 75 76 77 78 79 80 81 82 83 84 85 86 36 87 ...

output:

528
527
526
527
527
527
527

result:

ok 7 numbers

Test #10:

score: 0
Accepted
time: 21ms
memory: 8000kb

input:

10
100000
1 1 2 2 2 3 4 5 6 7 8 6 8 9 10 11 12 13 14 15 16 17 22 18 19 20 21 22 23 8 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 27 39 40 41 42 43 44 45 46 39 39 48 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 59 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89...

output:

439
439
441
439
441
441
442
441
441
440

result:

ok 10 numbers

Test #11:

score: 0
Accepted
time: 21ms
memory: 9932kb

input:

15
66666
1 2 3 1 2 3 4 5 6 1 7 8 9 10 2 11 12 13 14 15 16 17 18 19 20 21 19 22 23 24 25 26 27 34 28 29 30 31 32 33 34 10 35 36 37 38 39 40 41 42 22 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 57 20 62 63 64 65 66 67 68 69 70 71 77 72 73 74 75 76 77 78 79 80 81 82 83 77 84 85 86 87 88 89...

output:

360
358
359
359
359
359
359
360
359
360
359
361
358
360
359

result:

ok 15 numbers

Test #12:

score: 0
Accepted
time: 11ms
memory: 9780kb

input:

57
17543
1 1 2 2 3 5 4 5 6 3 7 8 9 10 3 1 4 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 25 32 33 34 35 36 37 38 39 3 40 41 42 43 44 45 46 47 48 6 49 50 51 52 53 54 55 56 57 58 26 59 60 61 62 63 64 65 66 67 68 69 69 17 70 71 72 73 74 75 76 77 78 79 80 81 54 82 83 84 85 86 87 88 89 ...

output:

181
182
181
182
182
183
183
183
182
183
183
182
181
184
183
183
182
181
181
183
182
183
181
183
182
182
182
183
183
183
180
182
183
183
182
181
181
181
183
183
182
182
180
182
181
183
182
182
183
183
183
181
180
181
181
182
183

result:

ok 57 numbers

Test #13:

score: 0
Accepted
time: 18ms
memory: 7600kb

input:

100
10000
1 2 2 2 3 5 3 4 5 6 7 8 9 10 11 12 13 14 15 9 8 16 17 18 19 20 2 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 11 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 3 49 19 21 13 61 62 63 64 65 66 67 68 69 20 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8...

output:

136
138
138
136
135
137
136
136
137
138
137
137
138
138
138
137
137
137
138
137
137
136
138
136
138
138
138
137
137
138
137
136
136
137
137
137
137
138
137
136
137
138
136
136
138
138
136
137
137
138
136
137
137
138
137
138
137
138
136
135
138
137
136
137
134
137
137
136
137
137
135
136
138
138
136
...

result:

ok 100 numbers

Test #14:

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

input:

1000
1000
1 1 2 3 5 4 5 5 9 6 7 8 9 10 11 12 13 17 9 14 15 16 17 18 1 19 20 21 22 23 24 25 3 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 30 43 44 45 46 47 48 49 50 51 8 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 70 71 50 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9...

output:

43
42
42
42
41
41
42
41
42
42
41
42
42
42
42
41
42
41
42
42
42
41
42
41
42
42
42
40
43
40
42
42
40
42
42
42
41
41
42
41
41
41
42
42
42
41
42
41
42
42
42
42
42
42
41
42
43
41
40
41
42
42
42
43
42
40
41
42
42
41
41
41
42
42
43
41
41
41
42
40
42
42
42
42
41
42
42
42
42
43
41
41
42
41
41
41
42
42
42
42
...

result:

ok 1000 numbers

Test #15:

score: 0
Accepted
time: 11ms
memory: 7648kb

input:

10000
100
1 1 3 2 2 3 4 5 7 6 7 8 9 10 11 12 13 14 4 2 10 15 16 17 18 19 5 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 23 46 47 48 49 50 51 52 53 54 16 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 13 37 49 76 77 78 79 80 81 82 83 84 85 86
100
1 2 2...

output:

12
12
13
12
12
12
12
11
12
12
12
12
13
13
12
12
12
11
13
13
12
12
13
12
12
12
12
13
13
13
12
12
12
13
11
13
13
12
12
12
13
12
12
12
12
12
12
12
12
11
12
13
11
13
12
12
12
12
12
12
12
13
12
12
12
11
12
12
13
13
12
13
12
13
12
11
12
11
11
12
13
12
13
12
12
13
12
12
12
12
12
12
12
12
12
12
12
11
12
13
...

result:

ok 10000 numbers

Test #16:

score: 0
Accepted
time: 14ms
memory: 7668kb

input:

100000
10
1 2 1 2 3 4 5 6 7
10
1 1 1 2 3 6 4 5 6
10
1 1 3 2 3 1 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 2 3 1 2 3 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 1 2 4 3 4 5 6 7
10
1 1 1 2 3 4 5 6 7
10
1 2 2 4 3 3 4 5 6
10
1 2 1 2 3 4 5 6 7
10
1 1 3 2 3 6 4 5 6
10
1 2 2 4 3 2 4 5 6
10
1 1 1 2 3 5 4 5 6
10
1 2 2 4 3 4 5 6 7...

output:

3
4
4
3
3
3
3
3
3
3
4
3
4
3
4
4
3
3
3
3
3
4
4
4
4
3
3
3
3
3
4
4
4
4
3
3
3
3
3
4
3
4
4
3
3
4
3
3
4
3
4
3
3
3
3
3
4
3
3
3
3
4
3
3
3
3
3
4
3
3
4
3
4
4
3
3
4
3
3
4
3
3
3
4
4
3
3
3
3
3
4
3
4
4
3
3
3
3
4
3
4
3
3
4
3
3
4
3
4
4
3
3
4
4
4
3
3
3
3
3
4
3
3
3
4
3
4
3
3
3
3
4
3
4
3
4
3
4
3
4
3
3
3
4
4
3
4
4
3
3
...

result:

ok 100000 numbers