Odd-Cost Assignments on a Deepest Tree Path

# Odd-Cost Assignments on a Deepest Tree Path You are given an undirected tree with `n` nodes labeled from `1` through `n`, rooted at node `1`. The array `edges` contains its `n - 1` edges as pairs `[u, v]`. Initially, every edge has weight zero. Select any one node `x` at maximum depth, where depth is the number of edges from the root. Assign each edge on the path from node `1` to `x` a weight of either `1` or `2`. Return the number of assignments for which this path's total weight is odd, modulo `1000000007`. Ignore all edges outside the selected path. If several deepest nodes exist, choose one; the choice of node is not an additional object being counted. ### C++ Interface ```cpp class Solution { public: int assignEdgeWeights(vector<vector<int>>& edges); }; ``` The number of nodes is `edges.size() + 1`. ### Examples **Example 1** ```text edges = [[1,2],[2,3],[3,4],[2,5]] Output: 4 ``` The deepest node is `4`, and its root path is `1 -> 2 -> 3 -> 4`. The odd-cost weight sequences along those three edges are `(1,1,1)`, `(1,2,2)`, `(2,1,2)`, and `(2,2,1)`. Edge `[2,5]` is ignored. **Example 2** ```text edges = [[1,2],[1,3],[1,4]] Output: 1 ``` Any of nodes `2`, `3`, or `4` can be selected. For one selected path, its single edge must receive weight one. The other two edges do not contribute extra assignments, and the three possible choices of endpoint are not added together. ### Constraints - `2 <= n <= 100000`. - `edges.length == n - 1`. - Each entry is `[u, v]` with `1 <= u, v <= n`. - The edges form a valid tree. - Every relevant edge receives weight one or two; only the selected root-to-deepest-node path is counted. ### Clarifying Questions - Is depth measured using assigned weights? No. It is the number of tree edges from node one. - Are assignments outside the selected path included in the count? No. The task explicitly ignores those edges. - Should the answers for all deepest nodes be summed? No. Select one deepest node and count assignments on that path. - Are the edge pairs directed away from the root? No. They describe undirected edges in any input order. ### What a Strong Answer Covers - Correct interpretation of the root, maximum depth, and odd total path cost. - Counting assignments for one selected path without counting endpoint choices or off-path edges. - Correct behavior for branching trees, tied deepest nodes, and long chains. - Correct counts modulo 1000000007 and resource bounds for trees with up to 100000 nodes. ### Follow-up Questions - How should two full-tree assignments that differ only outside the selected path be treated under this task's counting rule? - How does selecting a deepest endpoint differ from counting the endpoint itself as part of an assignment? ```hint Count path assignments First find the maximum root depth using an iterative tree traversal. For a path with D edges, assign the first D-1 weights freely and determine which final weight makes the total odd. Off-path edges and the number of deepest nodes do not enter this count. ```