## Problem You are given an integer array `parent` of length `n` describing a directed parent pointer for each node `i` (nodes are labeled `0..n-1`). - `parent[i]` is the parent of node `i`. - Exactly one node should be the root, indicated by `parent[root] = -1`. Determine whether these `n` nodes form a **valid rooted tree**. A valid rooted tree must satisfy all of the following: 1. **Exactly one root** (exactly one index `i` with `parent[i] = -1`). 2. **No cycles** (following parent pointers from any node must eventually reach the root). 3. **Connectivity** (every node is reachable from the root; equivalently, every node has exactly one simple path to the root). ## Input - `parent`: integer array of length `n` where each value is either `-1` or in `[0, n-1]`. ## Output - Return `true` if `parent` represents a valid rooted tree; otherwise return `false`. ## Notes / Edge Cases - `n` can be 1 (then the only valid tree is `parent[0] = -1`). - Self-parenting like `parent[i] = i` is invalid. - Multiple `-1` entries (multiple roots) is invalid. - A cycle among non-root nodes is invalid. - A disconnected component (some nodes not reachable from the root) is invalid.

def solution(parent):
    n = len(parent)
    if n == 0:
        return False

    root = -1
    root_count = 0
    children = [[] for _ in range(n)]

    for i, p in enumerate(parent):
        if p == -1:
            root_count += 1
            root = i
        else:
            if p < 0 or p >= n:
                return False
            children[p].append(i)

    if root_count != 1:
        return False

    visited = [False] * n
    stack = [root]
    visited[root] = True
    seen = 0

    while stack:
        node = stack.pop()
        seen += 1
        for child in children[node]:
            if visited[child]:
                return False
            visited[child] = True
            stack.append(child)

    return seen == n