QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#746234#9751. 覆盖一棵树wsyear#AC ✓29ms38120kbC++201.1kb2024-11-14 13:56:042024-11-14 13:56:05

Judging History

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

  • [2024-11-14 13:56:05]
  • 评测
  • 测评结果:AC
  • 用时:29ms
  • 内存:38120kb
  • [2024-11-14 13:56:04]
  • 提交

answer

#include <bits/stdc++.h>

#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

template<class T>inline void chkmn(T &x, T y) { if (y < x) x = y; }
template<class T>inline void chkmx(T &x, T y) { if (y > x) x = y; }

using namespace std;

const int maxn = 200010;

int n, fa[maxn], f[maxn], mx;
vector<int> e[maxn];

void dfs(int u) {
  if (!SZ(e[u])) return f[u] = 0, void();
  f[u] = 0;
  vector<int> vec;
  for (int v : e[u]) {
    dfs(v), f[v]++;
    vec.emplace_back(f[v]);
  }
  sort(ALL(vec));
  f[u] = vec[0], chkmx(mx, f[u] + (u != 1));
}

void work() {
  cin >> n;
  rep (i, 1, n) e[i].clear();
  rep (i, 2, n) cin >> fa[i], e[fa[i]].emplace_back(i);
  mx = 0, dfs(1);
  cout << mx << '\n';
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  int t; cin >> t;
  while (t--) work();
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 13ms
memory: 5576kb

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: 13ms
memory: 5880kb

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: 16ms
memory: 6024kb

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: 7132kb

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: 16ms
memory: 20160kb

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: 24ms
memory: 28548kb

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: 22ms
memory: 29660kb

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: 22ms
memory: 13080kb

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: 6ms
memory: 8032kb

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: 29ms
memory: 14484kb

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: 11ms
memory: 9328kb

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: 23ms
memory: 14412kb

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: 23ms
memory: 9192kb

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: 13ms
memory: 5648kb

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

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: 23ms
memory: 38120kb

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