Time Taken to Mark All Nodes
hard · 27.6% accepted · 139 likes · top 6%
dynamic programming · tree · depth-first search · graph theory
Description
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.
Initially, all nodes are unmarked. For each node i:
- If i is odd, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 1.
- If i is even, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 2.
Return an array times where times[i] is the time when all nodes get marked in the tree, if you mark node i at time t = 0.
Note that the answer for each times[i] is independent, i.e. when you mark node i all other nodes are unmarked.
Solution