Linear time labeling algorithm for a tree?
Unrooted Trees

You can use a priority queue to solve this in $O(E+V\log V)$:


Put all vertices in a priority queue, with their priority being their degree.
While the queue is non-empty:

Remove a vertex $v$ of minimal priority, which must be $1$ (or $0$ at the very end).
Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
Subtract $1$ from the priority of the unique remaining neighbor of $u$ (if any).



In fact, we don't really need a priority queue, and this algorithm can be implemented using a simple queue in time $O(E+V)$:


Initialize an array of length $V$ with the degrees of all vertices.
Initialize another array of length $V$ with "alive".
Go once through the first array, and push all vertices of degree $1$ to a queue.
While the queue is non-empty:

Pop a vertex $v$.
Let $\sigma(v) = 1 + \max \sigma(u)$, where $u$ goes over all original neighbors of $v$.
Mark $v$ as "dead".
If $v$ has some "alive" neighbor $u$, subtract $1$ from the degree of $u$.
If the new degree of $u$ is $1$, push $u$ to the queue.



Rooted Trees

Use DFS instead. Here is a sketch of the algorithm.


Given a node $v$, if $v$ is a leaf, set $d(v) = 1$.
If $v$ is not a leaf, run the algorithm on all its children, and then let $d(v) = 1 + \max d(u)$, where $u$ goes over the set of all children.


You run this algorithm on the root.