Village Guilds

We need count distinct sets of the form:

$$G(v,h)=\{u \mid u \text{ is in subtree of } v,\ depth[u]=depth[v]+h\}.$$

So yeah, it is just a subtree sliced by one global depth level.

The Trap

There are up to $O(n^2)$ possible pairs $(v,h)$, but many of them describe the same set.

Example: if $v$ has only one child branch that reaches the target depth, then the guild from $v$ is identical to the guild from that child. Choosing the higher vertex added absolutely nothing. Classic fake complexity nonsense.

Suppose we want depth $d$. For vertex $v$, look at which children of $v$ have descendants at depth $d$.

• If exactly one child contributes, then $G(v,d-depth[v])$ equals the same slice from that child.
• If zero children contribute and $d>depth[v]$, the guild is empty, so we ignore it.
• If at least two children contribute, then this is a genuinely new non-singleton guild whose LCA is exactly $v$.
• If $d=depth[v]$, the guild is just $\{v\}$.

All singleton guilds are distinct, so they contribute exactly $n$.

Now we only need count the non-singleton guilds.

Canonical Form

Take any non-empty guild. If it is not a singleton, start from its chosen vertex $v$ and target depth $d$.

If only one child of $v$ reaches depth $d$, move down into that child. The set does not change. Repeat.

Eventually, one of two things happens:

1. We reach depth $d$, so the set is a singleton.
2. We stop at some vertex $x$ where at least two children reach depth $d$.

In case 2, the set has LCA $x$, so no other vertex can be the canonical source of the same non-singleton set. Therefore every distinct non-singleton guild corresponds to exactly one pair $(x,d)$ such that at least two children of $x$ contain vertices at depth $d$.

So the answer is:

$$n + \sum_x \#\{d > depth[x] : \text{at least two children of } x \text{ reach depth } d\}.$$

Counting Levels For One Vertex

For a child $c$ of $x$, what depths can it contribute to?

The subtree of $c$ contains some vertex at every depth from $depth[c]$ down to its maximum descendant depth. Since trees are connected downward, a deepest path passes through every intermediate depth.

Let:

$$mx[c] = \max depth[u] \quad \text{over } u \text{ in subtree of } c.$$

Since $depth[c]=depth[x]+1$, child $c$ contributes to all depths in:

$$[depth[x]+1,\ mx[c]].$$

For vertex $x$, all child intervals start at the same point. A depth is covered by at least two children exactly when the second-largest value among $mx[c]$ is at least that depth.

So if the two largest child maximum depths are $a \ge b$, then the contributing depths are:

$$depth[x]+1,\ depth[x]+2,\ldots,\ b.$$

There are:

$$b-depth[x]$$

such depths, if $x$ has at least two children. If it has fewer than two children, it contributes $0$.

That is the whole problem. Compute subtree maximum depths, grab the second largest child maximum for every vertex, add it up, then add $n$.

Algorithm

1. Build the rooted tree from the parent list.
2. Compute $depth[v]$ for all vertices. Since $p_i<i$, reading order already gives this directly:

$$depth[i]=depth[p_i]+1.$$

3. Initialize $mx[v]=depth[v]$.
4. Process vertices from $n$ down to $1$ and update:

$$mx[parent[v]] = \max(mx[parent[v]], mx[v]).$$

5. Start answer as $n$ for all singleton guilds.
6. For every vertex, find the largest and second-largest $mx[c]$ among its children.
7. If the second largest exists, add:

$$secondLargest-depth[v].$$

Why This Is Correct

Every guild is a slice of a subtree at some depth. If the slice passes through only one child subtree, shifting the root to that child gives the exact same set. Repeating this makes every guild either a singleton or a slice from a vertex where at least two child subtrees participate.

Singletons are exactly the sets $\{v\}$, so there are $n$ of them.

For non-singletons, the canonical vertex is the LCA of all vertices in the guild. That makes the representation unique. A vertex $v$ creates one distinct non-singleton guild for every depth level reached by at least two of its children.

A child $c$ reaches exactly the depth levels from $depth[v]+1$ through $mx[c]$. Since all those intervals share the same left endpoint, the number of levels covered by at least two children is determined by the second largest $mx[c]$. That count is $secondLargest-depth[v]$.

Thus summing this value over all vertices and adding $n$ counts every distinct guild exactly once.

Complexity

Each edge is processed a constant number of times.

$$O(n)$$

per test case, with total $O(\sum n)$ over all tests. Memory is also $O(n)$.