Tree Eccentricity for Every Node

Given an undirected tree, return an array where answer[i] is the maximum distance from node i to any other node in the tree. This is a rerooting-style tree DP problem because distances can be propagated from parent to child after an initial DFS computes subtree contributions.

Input Format

n and edges describe a tree

Output Format

maximum distance from each node to any other node

Constraints

  • 1 <= n <= 10^5
  • edges.length = n-1
  • The edges array describes an undirected tree.

Examples

Example 1:

Input:

n = 5
edges = [[0,1],[1,2],[1,3],[3,4]]

Output:

[3,2,3,2,3]

Explanation:

Nodes 0, 2, and 4 are at distance 3 from the farthest node, while nodes 1 and 3 have eccentricity 2.

Example 2:

Input:

n = 4
edges = [[0,1],[1,2],[2,3]]

Output:

[3,2,2,3]

Explanation:

In a line, the endpoints have the largest eccentricity.

Loading...
Tree Eccentricity for Every Node