september (APIO contest)
Time limit: 1 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: graph theory, strongly connected component, union-find, data structures, dfs, tree, graph traversal

![](_page_0_Picture_0.jpeg)

# September

The central square of Hangzhou is home to a famous ancient tree, which can be regarded as a rooted tree with *N* nodes, indexed from 0 to *N* − 1, with node 0 being the root.

A node with no children is called a **leaf node**. Every time the ancient tree sheds its leaves, it selects one leaf node at that time to delete, and it may shed leaves multiple times in the same day.

There are *M* volunteers (indexed from 0 to *M* − 1) responsible for guarding the ancient tree. Each of them independently records the leaf-shedding situation of this year, using the following method:

Every day, collect the indices of all newly fallen leaves (i.e. the indices of the nodes which are deleted on that day), and write them down in any order after the previous fallen leaves.

For example: On the first day, leaves 3 and 4 fall, so they write down 3, 4 or 4, 3. On the second day, leaves 1 and 2 fall, so they continue to write down 1, 2 or 2, 1. The final record may be any of (3, 4, 1, 2), (4, 3, 1, 2), (3, 4, 2, 1), or (4, 3, 2, 1).

The process lasts for *K* days, with newly fallen leaves every day, until only the root node remains.

While traveling, you happen to visit Hangzhou. It is now a cold winter. Looking up at the bare branches of the ancient tree, you can't help but imagine the beautiful sight of falling leaves.

You are very curious to know how many days you could have seen falling leaves this year, but you can only find the records of the *M* volunteers. Try to infer the maximum possible value of *K* from the records.

# Implementation Details

You need to implement the following function:

```c++
int solve(int N, int M, std::vector<int> F,
          std::vector<std::vector<int>> S);
```

*   *N*: The number of nodes of the ancient tree.
*   *M*: The number of volunteers.
*   *F*: An integer array with a length of *N*. For 1 ≤ *i* ≤ *N* − 1, *F*[*i*] represents the index of the parent node of node *i*. *F*[0] is always −1.
*   *S*: An array containing *M* arrays. Each element of *S* is an integer array with a length of *N* − 1. *S*[*i*][*j*] represents the *j*-th index recorded by volunteer *i* (starting from 0).
*   The function must return an integer that represents the maximum possible value of *K* (i.e., the feasible maximum number of leaf-falling days) according to the above rules.
*   For each test case, the grader may call this function more than once. Each call should be processed as a separately new scenario.

**Note: Since the function will be called more than once, contestants need to pay attention to the impact of the remaining data of the previous call on the current call, especially the state stored in global variables.**

# Examples

## Example 1

Consider the following call:

```c++
solve(3, 1, {-1, 0, 0}, {{1, 2}});
```

The corresponding tree is shown below:

![](_page_1_Figure_10.jpeg)

Leaves 1 and 2 may fall on the same day, or 1 may fall first on the first day, followed by 2 on the second day. The leaf-falling days last no more than 2 days.

Therefore, the procedure should return 2.

## Example 2

Consider the following call:

```c++
solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}});
```

The corresponding tree is shown below:

![](_page_2_Figure_2.jpeg)

Assuming there are at least 2 leaf-falling days, according to the volunteers' records, leaf 4 will fall on different days (the first and last), which is contradictory.

Therefore, the procedure should return 1.

# Constraints

*   2 ≤ *N* ≤ 10<sup>5</sup>.
*   1 ≤ *M* ≤ 5.
*   ∑ *N* \* *M* ≤ 8 × 10<sup>5</sup>.
*   *F*[0] = −1. For 1 ≤ *i* ≤ *N* − 1, 0 ≤ *F*[*i*] ≤ *i* − 1.
*   For 0 ≤ *i* < *M*, array *S*[*i*] is a permutation of 1, 2, ..., *N* − 1.
*   It is guaranteed that *F* describes a rooted tree with node 0 being the root.

# Subtasks

1.  (11 points): *M* = 1, *N* ≤ 10, ∑ *N* ≤ 30.
2.  (14 points): *N* ≤ 10, ∑ *N* ≤ 30.
3.  (5 points): *M* = 1, *N* ≤ 1000, ∑ *N* ≤ 2000, *F*[*i*] = *i* − 1.
4.  (9 points): *M* = 1, *N* ≤ 1000, ∑ *N* ≤ 2000.
5.  (5 points): *N* ≤ 1000, ∑ *N* ≤ 2000, *F*[*i*] = *i* − 1.
6.  (11 points): *N* ≤ 1000, ∑ *N* ≤ 2000.
7.  (9 points): *M* = 1, *F*[*i*] = *i* − 1.
8.  (11 points): *M* = 1.
9.  (9 points): *F*[*i*] = *i* − 1.
10. (16 points): No additional constraints.

# Sample Grader

The sample grader reads the input in the following format:

*   Line 1: *T*

For each of the following *T* test cases:

*   Line 1: *N* *M*
*   Line 2: *F*[1] *F*[2] ⋯ *F*[*N* − 1]
*   Line 3 + *i* (0 ≤ *i* < *M*): *S*[*i*][0] *S*[*i*][1] *S*[*i*][2] ⋯ *S*[*i*][*N* − 2]

The sample grader prints your answers in the following format:

For each test case:

*   Line 1: the return value of solve

Starter code:
stub.cpp: #include "september.h"

#include <cassert>
#include <cstdio>
#include <vector>

void taskcase() {
	int N, M;
	assert(2 == scanf("%d%d", &N, &M));
	
	std::vector<int> F(N);
	F[0] = -1;
	for (int i = 1; i < N; ++i)
  		assert(1 == scanf("%d", &F[i]));
	
	std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N - 1; ++j)
  			assert(1 == scanf("%d", &S[i][j]));
  	
	printf("%d\n", solve(N, M, F, S));
}

int main() {
	int T;
	assert(1 == scanf("%d", &T));
	while(T--) taskcase();
	return 0;
}

september.cpp: #include "september.h"

#include <vector>

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S) {
	return 0;
}

september.h: #include <vector>

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S);


Grader code:
grader.cpp: #include "september.h"

#include <iostream>
#include <string>
#include <vector>

namespace mtbpdhr2zxjo1o4i9oreohsbuzzl4s6u
{
	int taskcase ()
	{
		int N, M; std::cin >> N >> M;
		std::vector<int> F(N); F[0] = -1;
		for (int i = 1; i < N; i++) std::cin >> F[i];
		std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
		for (int i = 0; i < M; i++) for (int j = 0; j < N - 1; j++) std::cin >> S[i][j];
		return solve(N, M, F, S);
	}

	int mian ()
	{
		std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr);
		std::string s; std::cin >> s;
		if (s != "txy4h26c1rm1uv8tr3eonahd67u8h56x")
		{
			std::cout << "7ckgnn4wyi495puj3ibqf81dqvapyv6b" << std::endl;
			std::cout << "Invalid Input" << std::endl;
			exit(0);
		}
		int T; std::cin >> T; std::vector<int> A(T);
		for (int i = 0; i < T; i++) A[i] = taskcase();
		std::cout << "7ckgnn4wyi495puj3ibqf81dqvapyv6b" << std::endl;
		for (int i = 0; i < T; i++) std::cout << A[i] << "\n";
		return 0;
	}
}

int main () {return mtbpdhr2zxjo1o4i9oreohsbuzzl4s6u::mian();}
september.h: #include <vector>

int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S);

stub.cpp: #include "september.h"

#include <cassert>
#include <cstdio>
#include <vector>

void taskcase() {
	int N, M;
	assert(2 == scanf("%d%d", &N, &M));
	
	std::vector<int> F(N);
	F[0] = -1;
	for (int i = 1; i < N; ++i)
  		assert(1 == scanf("%d", &F[i]));
	
	std::vector<std::vector<int>> S(M, std::vector<int>(N - 1));
	for (int i = 0; i < M; ++i)
		for (int j = 0; j < N - 1; ++j)
  			assert(1 == scanf("%d", &S[i][j]));
  	
	printf("%d\n", solve(N, M, F, S));
}

int main() {
	int T;
	assert(1 == scanf("%d", &T));
	while(T--) taskcase();
	return 0;
}


Setup script:

Evaluation script: