Wireless is the New Fiber
This problem asks us to construct a tree where the degree of a as many vertices as possible matches some input. It makes sense to break this problem into a few parts:
- What properties does a tree have?
- how can we make assignments of degrees to nodes such as to suit that property?
- Can we actually construct a tree with arbitrary degrees which satisfy the property in 1?
On the first question, we know the following about trees:
- They have n-1 edges (so total degrees is 2n-2)
- Each node has a degree of at least 1
On the second question: Since the graph is initially connected, the total number of degrees must exceed 2n-2, and each edge already has degree of at least 1. So we need to determine which to change. Naturally it makes sense to start with the largest nodes, since that takes away the most while only costing us a single node changing. We change each largest node to 1 until we get to 2n-2 (or more than 1 if changing it to 1 would make us go under 2n-2).
On the third: Separate the nodes into 2 sets: leaf nodes and non-leaf nodes (leaf nodes have degree 1). Assemble all the non-leaf nodes in a chain and then fill out the remaining edges with leaf nodes. Assuming the total sum of degrees is 2n-2, there will be exactly enough leaf nodes.