Leetcode 3559. Number of Ways to Assign Edge Weights II

Count assignments on the simple path between two nodes so that the sum of edge weights (each either 1 or 2) is odd — equivalently you need an odd number of edges labeled 1, so for a path of k edges the answer is 0 if k=0 else 2^{k-1} mod 1e9+7; the algorithmic challenge is computing k (the distance in edges) quickly for many queries (e.g., with LCA/depth preprocessing).