Table of Contents

ExplanationImplementation

Official Editorial

Explanation

Let's focus on one tree and its diameter first, naming the two endpoints E1E_1 and E2E_2. For every vertex vv on this tree, p[v]p[v] is either equal to E1E_1 or E2E_2, which we can show as proved here.

Additionally, even if the tree has multiple diameters, only the points with the lowest ID are taken, still resulting in two unique points showing up for each tree.

So, we can count the number of distinct vertices in PP and divide by two to find the number of trees, being careful to count the case where P[i]P[i] = ii as one tree, since it is just an isolated vertex to be counted as one tree.

Implementation

Time Complexity: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int n;
	cin >> n;
	// Array storing whether vertices have been visited
	vector<bool> visited(n);
	int ans = 0;
	for (int i = 0; i < n; i++) {

Python

n = int(input())
nums = list(map(int, input().split()))


# Array storing whether vertices have been visited
visited = [False] * n
ans = 0


for i in range(n):
	if i + 1 == nums[i]:
		ans += 2
	elif not visited[nums[i] - 1]:
		ans += 1
		visited[nums[i] - 1] = True


print(ans // 2)

Java

import java.io.*;
import java.util.StringTokenizer;


public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);


		int n = Integer.parseInt(r.readLine());
		// Array storing whether vertices have been visited

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum