Number of Ways to Assign Edge Weights I
DFS depth · parity argument · modular fast power · LC #3558
Medium
Cases
init
build
dfs
path
parity
fastpow
done
Problem

Undirected tree rooted at node 1. Assign each edge weight 1 or 2. Find the number of ways to assign weights on the path from root to a deepest node such that the path cost is odd.

Answer = 2depth−1 mod 109+7
Tree
Path★ Deepest
1root2
Parity table will appear in the parity phase.
Speed900ms
Progress1/15
Step Log
initNOW

Tree has 2 nodes, 1 edges. Root = 1. We need the max depth from root.

Live Stats
Max Depth
0
Answer
?
Complexity
Time
O(n)
Space
O(n)

Single DFS for max depth. Then O(log d) for modular exponentiation.

Steps
Now
1
Total
15
Left
14