Implementation - Preprocessing

Run a DFS to compute size[v], depth[v], and parent[v] for each node:

function dfs_init(v, par, d)
    parent[v] := par
    depth[v] := d
    size[v] := 1
    for u in adj[v]
        if u != par then
            dfs_init(u, v, d + 1)
            size[v] := size[v] + size[u]

Call $dfs\_init(root, -1, 0)$ from the root. This single DFS computes all three arrays in $O(n)$ time. You traverse each edge exactly twice, once in each direction.

Space complexity is $O(n)$ for the data structures used.