We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Time Taken to Mark All Nodes

Number: 3532

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an undirected tree with n nodes (indexed 0 to n – 1) and an array of edges, we “mark” nodes in a special way. When a starting node is marked at time t = 0 (and all other nodes are unmarked), every other node is marked according to its parity: • If a node is odd, it becomes marked at time x if at least one of its neighbors was marked at time x – 1. • If a node is even, it becomes marked at time x if at least one of its neighbors was marked at time x – 2. For each possible starting node, we want to compute the time at which all nodes become marked.

Note that in the marking process the cost to “reach” a vertex depends on that vertex’s parity. In other words, if we imagine “traveling” from the starting node to some other node along the unique tree path, every time we “enter” a node the cost incurred is 1 if that node is odd and 2 if it is even. The answer for a starting node is the maximum distance (i.e. maximum sum of such costs along some path) from it to any other vertex.

Key Insights

  • The propagation rule can be “translated” into a weighted distance on the tree: starting at node s (with cost 0), when moving to any neighbor v the cost is: 1 if v is odd, 2 if v is even.
  • For a fixed starting node s, the marking time for any other node is the sum of the cost values for all vertices along the unique path from s (excluding s).
  • The answer for starting node s is the “eccentricity” – the maximum weighted distance from s.
  • A naive BFS/DFS from every node is too slow (O(n²)); instead, we use a tree re‐rooting dynamic programming method.
  • In our DP formulation we “assign” the cost to a vertex (other than the source) and compute two values: • dp[u] – the maximum “downward” (subtree) distance from u. • up[u] – the best distance that comes from outside u’s subtree (through its parent).
  • Finally, for each vertex u considered as the starting node, the answer is max(dp[u], up[u]).

Space and Time Complexity

Time Complexity: O(n) (each node is visited a constant number of times) Space Complexity: O(n) (to store the tree, dp/up arrays, and recursion stack)

Solution

We first “root” the tree arbitrarily (for example, at node 0). For each vertex u we define dp[u] as the maximum additional cost to mark a vertex in u’s subtree—that is, for any direct child v of u the candidate cost is cost(v) + dp[v] where cost(v) = 1 if v is odd and 2 if v is even. (If u is a leaf then dp[u] = 0.)

Next, we perform a second DFS to compute up[u] for each node u (the maximum cost you can obtain by going “upward” from u – meaning through its parent and some branch outside the subtree of u). For a child v of u the candidate upward contribution comes from the maximum of: • up[u] (coming from above u) and • the best “downward” candidate from u among all children other than v. Since we then “go back” from v to u, an extra cost cost(u) is incurred in that reversal. Hence, we update: up[v] = cost(u) + max( up[u], (if v was the best child of u then use second best candidate else the best candidate) ).

Finally, for each node u considered as the starting node, the answer is the maximum distance we can obtain – namely: ans[u] = max(dp[u], up[u]). This value is the time at which the final node gets marked.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java. In each solution the following variables are used: • tree – the adjacency list of the tree. • dp – the maximum downward distance from a node. • up – the best distance coming from above. • bestDown and secondDown – for each node, the best two downward candidates among its children (each candidate is cost(child)+dp[child]). • cost(v) – assigned as 1 if v is odd and 2 if v is even.

# Python solution
import sys
sys.setrecursionlimit(10**6)

def timeToMarkAllNodes(n, edges):
    # Build the tree as an adjacency list.
    tree = [[] for _ in range(n)]
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # cost for marking a node v (v != source) based on its parity.
    def cost(v):
        return 1 if v % 2 == 1 else 2

    dp = [0] * n
    bestDown = [0] * n   # best candidate (cost(child) + dp[child]) among children
    secondDown = [0] * n # second best candidate

    # First DFS: post-order to compute dp[u]
    def dfs1(u, parent):
        for v in tree[u]:
            if v == parent:
                continue
            dfs1(v, u)
            candidate = cost(v) + dp[v]
            # Update best and second best for node u
            if candidate > bestDown[u]:
                secondDown[u] = bestDown[u]
                bestDown[u] = candidate
            else:
                secondDown[u] = max(secondDown[u], candidate)
        dp[u] = bestDown[u]
    
    dfs1(0, -1)

    # up[u] holds the best distance coming from parent's side.
    up = [0] * n
    ans = [0] * n
    # Second DFS: Pre-order to compute up[v] for children.
    def dfs2(u, parent):
        # The answer for u (when u is taken to be the starting node)
        ans[u] = max(dp[u], up[u])
        for v in tree[u]:
            if v == parent:
                continue
            # For u, choose best candidate excluding v.
            candidate = bestDown[u]
            # Determine if the best candidate came from child v.
            if cost(v) + dp[v] == bestDown[u]:
                candidate = secondDown[u]
            # Compute up[v]: go from v -> u (add cost(u)) and then take the best from parent's side.
            up[v] = cost(u) + max(up[u], candidate)
            dfs2(v, u)
    
    dfs2(0, -1)

    # Since the answer for each starting node s is the maximum distance obtainable,
    # we need to re-root the tree at every node.
    # We have computed ans[u] when the tree is rooted at 0.
    # However, the DP is designed to work for all nodes.
    return ans

# Example usage:
if __name__ == "__main__":
    # Example 1:
    n1 = 3
    edges1 = [[0,1],[0,2]]
    print(timeToMarkAllNodes(n1, edges1))  # Expected Output: [2,4,3]
← Back to All Questions