Odd-Cost Edge Assignments for Tree Paths

# Odd-Cost Edge Assignments for Tree Paths You are given an undirected tree rooted at node `1`, with nodes labeled `1` through `n`. Its `n - 1` edges are listed in `edges` as pairs `[u, v]`. Initially, all edge weights are zero. For each query `[u, v]`, consider the unique path between those two nodes. Assign every edge on that path a weight of either `1` or `2`, and count the assignments whose total path weight is odd. Ignore every edge outside that query's path. Return one count per query, in order, modulo `1000000007`. Each query is a separate counting task. ### C++ Interface ```cpp class Solution { public: vector<int> assignEdgeWeights(vector<vector<int>>& edges, vector<vector<int>>& queries); }; ``` The number of nodes is `edges.size() + 1`. ### Examples **Example 1** ```text edges = [[1,2],[2,3],[2,4],[4,5]] queries = [[3,5],[1,5],[2,2],[4,5]] Output: [4,4,0,1] ``` The first two paths are `3 -> 2 -> 4 -> 5` and `1 -> 2 -> 4 -> 5`, each with three edges. Their odd-cost weight sequences are `(1,1,1)`, `(1,2,2)`, `(2,1,2)`, and `(2,2,1)`. The path from node two to itself has no edges and total cost zero. On the final single-edge path, only weight one gives an odd cost. **Example 2** ```text edges = [[1,2],[1,3],[1,4],[1,5]] queries = [[2,5],[1,4],[5,2]] Output: [2,1,2] ``` Each leaf-to-leaf path in these queries has two edges, whose odd-cost assignments are `(1,2)` and `(2,1)`. The root-to-leaf query has one edge. Off-path edges do not multiply any count, and reversing the endpoints leaves the count unchanged. ### Constraints - `2 <= n <= 100000` and `edges.length == n - 1`. - `1 <= queries.length <= 100000`. - Each edge and query contains two node labels in `[1, n]`. - `edges` forms a valid tree. - Each relevant edge is assigned weight one or two; answers count only assignments on the queried path. ### Clarifying Questions - What is returned for `[u, u]`? Zero. Its empty path has total weight zero, which is even. - Are off-path weights additional choices? No. Those edges are disregarded. - Are the edge pairs directed? No. They represent an undirected tree in any input order. - Does one query choose weights that restrict the next query? No. Each query asks for its own count of valid assignments. ### What a Strong Answer Covers - Correct path-specific counts, without including off-path assignments. - Exact behavior for self-queries, neighboring nodes, and reversed endpoints. - Safe modulo arithmetic and correct node labels rooted at one. - A correctness argument and resource bounds for up to 100000 nodes and queries, including a long chain. ### Follow-up Questions - Why do assignments differing only outside the queried path represent the same relevant choice here? - Can reversing a query's endpoints change the number of odd-cost assignments? Explain from the path definition. ```hint Separate the two counts Find the number D of edges on each query path using depths and a lowest-common-ancestor structure. For D positive, choosing weights on the first D-1 edges leaves exactly one final weight that makes the sum odd. Handle the empty path separately. ```