CF1675D Vertical Paths

You are given a rooted tree consisting of $ n $ vertices. Vertices are numbered from $ 1 $ to $ n $ . Any vertex can be the root of a tree. A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root. The tree is specified by an array of parents $ p $ containing $ n $ numbers: $ p_i $ is a parent of the vertex with the index $ i $ . The parent of a vertex $ u $ is a vertex that is the next vertex on the shortest path from $ u $ to the root. For example, on the simple path from $ 5 $ to $ 3 $ (the root), the next vertex would be $ 1 $ , so the parent of $ 5 $ is $ 1 $ . The root has no parent, so for it, the value of $ p_i $ is $ i $ (the root is the only vertex for which $ p_i=i $ ). Find such a set of paths that: - each vertex belongs to exactly one path, each path can contain one or more vertices; - in each path each next vertex — is a son of the current vertex (that is, paths always lead down — from parent to son); - number of paths is minimal. For example, if $ n=5 $ and $ p=[3, 1, 3, 3, 1] $ , then the tree can be divided into three paths: 1. $ 3 \rightarrow 1 \rightarrow 5 $ (path of $ 3 $ vertices), 2. $ 4 $ (path of $ 1 $ vertices). 3. $ 2 $ (path of $ 1 $ vertices). Example of splitting a root tree into three paths for $ n=5 $ , the root of the tree — node $ 3 $ .

N/A

N/A