Tree Permutations

You are given a tree with $N$ nodes (numbered $1$ through $N$), rooted at node $1$. For each valid $i$, node $i$ has a value $a_i$ written on it. An undirected simple path between any two nodes $u$ and $v$ is said to be vertical if $u=v$ or $u$ is an ancestor of $v$ or $v$ is an ancestor of $u$. Let's define a *vertical partition* of the tree as a set of vertical paths such that each node belon