The Nested Fractal Path
A young programmer, inspired by fractals, designed a special tree structure. Each node represents a command, and edges represent the flow of execution. Starting at the root (node 0), you can follow any path downwards. However, if you reach a node with multiple children, you must choose one path and 'commit' to it, meaning you can't backtrack to explore other branches from that node. You want to find the total number of distinct paths from the root to any leaf node, adhering to this 'commit' rule. A path is defined by the sequence of nodes visited. How many such distinct paths exist?
Input
The first line contains an integer N, the number of nodes (0 to N-1). The next N-1 lines each contain two integers U and V, representing an undirected edge between node U and node V. Node 0 is guaranteed to be the root.
Output
Print a single integer: the total number of distinct paths from the root to any leaf.
Constraints
1 <= N <= 200000. The graph is guaranteed to be a tree.
Example 1
4 0 1 0 2 1 3
2
Paths: 0->1->3, 0->2. Total 2 paths.
Example 2
5 0 1 0 2 0 3 0 4
4
Paths: 0->1, 0->2, 0->3, 0->4. Total 4 paths.
Hints
Similar problems
- Longest Increasing Subsequence on a PermutationHard
- Maximum Sum Non-Adjacent PairsMedium
- Find Minimum Depth Binary TreeMedium
- Lexicographically Smallest PathMedium
- Maximum Depth Path SumMedium
- Sum of Subtree SizesEasy
More topics: Dynamic Programming problems, Trees problems, Recursion problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 0 1 0 2 1 3
5 0 1 0 2 0 3 0 4