Search⌘ K
AI Features

Solution: Collect Coins in a Tree

Understand how to solve the coin collection problem in an undirected tree through a two-phase pruning process using topological sort. Explore how removing zero-coin leaf branches and the outermost two layers reduces path traversal. Gain skills in graph representation, leaf node pruning, and calculating minimal edges to traverse while ensuring all coins are collected and you return to your start.

Statement

You are given an undirected, unrooted tree with n nodes indexed from 00 to n1n - 1. The tree structure is defined by a 22D integer array edges of length n1n - 1, where edges[i] = [a_i, b_i] indicates an undirected edge between nodes a_i and b_i. You are also given a binary array coins of size n, where coins[i] is either 00 or 11 ...