Problem statement

An undirected tree has n nodes labelled 0 to n - 1; its n - 1 edges are given in edges, each [ui, vi].

At time 0 you mark exactly one node. From then on, every unmarked node gets marked by this rule:

• an odd node i is marked at time x if at least one neighbour was marked at time x - 1;
• an even node i is marked at time x if at least one neighbour was marked at time x - 2.

Return an array times where times[i] is the moment the last node gets marked when you start by marking node i alone at time 0. Each times[i] is answered independently.

Example 1

Input: edges = [[0,1],[0,2]]
Output: [2,4,3]
Explanation: Start at 0: node 1 (odd) is marked at 1, node 2 (even) at 2. Start at 1: node 0 (even) at 2, then node 2 (even) at 4. Start at 2: node 0 at 2, node 1 at 3.

Example 2

Input: edges = [[0,1]]
Output: [1,2]

Example 3

Input: edges = [[2,4],[0,1],[2,3],[0,2]]
Output: [4,6,3,5,5]

Constraints

• 2 <= n <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• the input is a valid tree

Hints for Time Taken to Mark All Nodes

1. Hint 1

   Marking spreads along tree paths, and stepping into node v always costs the same: 1 if v is odd, 2 if it is even. So times[i] is the longest weighted path starting at i.

2. Hint 2

   Computing that from every start is O(n²). Root the tree once; the farthest node from i is either below i or reached by first going up to its parent.

3. Hint 3

   For each node keep the two best downward values coming from different children, so a child can ask its parent for the best path that does not come back through itself — then up[child] = w(parent) + max(up[parent], best of parent excluding child).

How to solve Time Taken to Mark All Nodes

Put the cost on the node you step into: entering an odd node costs 1, an even node 2. Then times[i] is the maximum weighted distance from i, and the classic two-pass re-rooting DP gives every node's farthest distance in linear time.

Approach

1. Root the tree at 0 and record a BFS order with parents.
2. Bottom-up (reverse BFS order): for each child c of p, the candidate down[c] + w(c) updates p's best and second-best downward values, remembering which child gave the best.
3. Top-down (BFS order): for each child c of p, the best path from c that starts by stepping to p is w(p) + max(up[p], other), where other is p's best downward value from a child other than c.
4. times[u] = max(down[u], up[u]).

Why it works

Every path from u either stays inside u's subtree (covered by down[u]) or leaves through the parent. A path through the parent p then continues either further up (up[p]) or down into a sibling subtree — which is exactly the best child value of p not using u. Keeping the top two child values is enough because only one child is excluded at a time.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The cost depends on the node being entered, not on the node you leave — the start node itself costs nothing.
• When the best child of p is c itself, c must use p's second-best value; otherwise it would count a path that walks back into its own subtree.
• Recursion over a 10^5-node path overflows the stack in several languages; use an explicit BFS order.

Reference solution

Python

from typing import List

def timeTaken(edges: List[List[int]]) -> List[int]:
    n = len(edges) + 1
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    parent = [-2] * n
    parent[0] = -1
    order = [0]
    for u in order:
        for v in adj[u]:
            if parent[v] == -2:
                parent[v] = u
                order.append(v)
    w = [1 if v % 2 == 1 else 2 for v in range(n)]
    d1 = [0] * n
    d2 = [0] * n
    c1 = [-1] * n
    for u in reversed(order):
        p = parent[u]
        if p >= 0:
            val = d1[u] + w[u]
            if val > d1[p]:
                d2[p] = d1[p]
                d1[p] = val
                c1[p] = u
            elif val > d2[p]:
                d2[p] = val
    up = [0] * n
    for u in order:
        p = parent[u]
        if p >= 0:
            other = d2[p] if c1[p] == u else d1[p]
            up[u] = w[p] + max(up[p], other)
    return [max(d1[u], up[u]) for u in range(n)]

Java

public static int[] timeTaken(int[][] edges) {
    int n = edges.length + 1;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    int[] parent = new int[n], order = new int[n], d1 = new int[n], d2 = new int[n], c1 = new int[n], up = new int[n], w = new int[n];
    for (int i = 0; i < n; i++) { parent[i] = -2; c1[i] = -1; w[i] = i % 2 == 1 ? 1 : 2; }
    parent[0] = -1;
    int tail = 0;
    order[tail++] = 0;
    for (int h = 0; h < tail; h++) {
        int u = order[h];
        for (int v : adj.get(u)) if (parent[v] == -2) { parent[v] = u; order[tail++] = v; }
    }
    for (int t = n - 1; t > 0; t--) {
        int c = order[t], p = parent[c];
        int val = d1[c] + w[c];
        if (val > d1[p]) { d2[p] = d1[p]; d1[p] = val; c1[p] = c; }
        else if (val > d2[p]) d2[p] = val;
    }
    for (int k = 1; k < n; k++) {
        int x = order[k], q = parent[x];
        int other = c1[q] == x ? d2[q] : d1[q];
        up[x] = w[q] + Math.max(up[q], other);
    }
    int[] ans = new int[n];
    for (int z = 0; z < n; z++) ans[z] = Math.max(d1[z], up[z]);
    return ans;
}

C++

vector<int> timeTaken(vector<vector<int>>& edges) {
    int n = edges.size() + 1;
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> parent(n, -2), d1(n, 0), d2(n, 0), c1(n, -1), up(n, 0), w(n), order;
    for (int i = 0; i < n; i++) w[i] = i % 2 == 1 ? 1 : 2;
    parent[0] = -1;
    order.push_back(0);
    for (size_t h = 0; h < order.size(); h++) {
        int u = order[h];
        for (int v : adj[u]) if (parent[v] == -2) { parent[v] = u; order.push_back(v); }
    }
    for (int t = n - 1; t > 0; t--) {
        int c = order[t], p = parent[c];
        int val = d1[c] + w[c];
        if (val > d1[p]) { d2[p] = d1[p]; d1[p] = val; c1[p] = c; }
        else if (val > d2[p]) d2[p] = val;
    }
    for (int k = 1; k < n; k++) {
        int x = order[k], q = parent[x];
        int other = c1[q] == x ? d2[q] : d1[q];
        up[x] = w[q] + max(up[q], other);
    }
    vector<int> ans(n);
    for (int z = 0; z < n; z++) ans[z] = max(d1[z], up[z]);
    return ans;
}

JavaScript

var timeTaken = function(edges) {
    var n = edges.length + 1;
    var adj = [], parent = [], d1 = [], d2 = [], c1 = [], up = [], w = [];
    for (var i = 0; i < n; i++) { adj.push([]); parent.push(-2); d1.push(0); d2.push(0); c1.push(-1); up.push(0); w.push(i % 2 === 1 ? 1 : 2); }
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    parent[0] = -1;
    var order = [0];
    for (var h = 0; h < order.length; h++) {
        var u = order[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (parent[v] === -2) { parent[v] = u; order.push(v); }
        }
    }
    for (var t = n - 1; t > 0; t--) {
        var c = order[t], p = parent[c];
        var val = d1[c] + w[c];
        if (val > d1[p]) { d2[p] = d1[p]; d1[p] = val; c1[p] = c; }
        else if (val > d2[p]) d2[p] = val;
    }
    for (var k = 1; k < n; k++) {
        var x = order[k], q = parent[x];
        var other = c1[q] === x ? d2[q] : d1[q];
        up[x] = w[q] + Math.max(up[q], other);
    }
    var ans = [];
    for (var z = 0; z < n; z++) ans.push(Math.max(d1[z], up[z]));
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More dynamic programming problems

• Maximum Path Sum Between Two Leaves Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Maximum Sum BST in Binary Tree Hard
• Recover a Tree From Preorder Traversal Hard
• Vertical Order Traversal of a Binary Tree Hard
• Binary Tree Cameras Hard