All Tracks Algorithms Dynamic Programming Dynamic Programming and Bit Masking Problem

Micro and Tree
Tag(s):

Data Structures, Dynamic Programming, Medium

Problem
Editorial
Analytics

Micro is having a tree which is having N nodes. Micro can perform some operations on the tree. In one operation he can select a node and remove it along with the entire subtree rooted at it, from its current position and attach it as child of some other node. He defines a functions \(f(X)\) on the tree, as the minimum number of operations needed to be done to make a straight chain of nodes out of the given tree, when the tree is rooted at node X. Now Micro wants to find out the minimum of all the \(f(i)\) where \(1 \le i \le N\).

Input:
First line consists of a single integer denoting N.
Following \(N-1\) lines consists of two space separated integers X and Y denoting there is an edge between nodes X and Y.

Output:
Print the required answer.

Constraints:
\(1 \le N \le 16\)
\(1 \le X, Y \le N\)

SAMPLE INPUT
5
1 2
1 3
2 4
2 5
SAMPLE OUTPUT
1
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Moonfrog Labs

Challenge Name

Moonfrog Labs Backend Hiring Challenge

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?