All submissions for this problem are available.
There is an unrooted tree, T, with L leaves and N nodes. (Leaves are nodes with degree = 1.)
For every node u, we define its rootScore. To calculate rootScore(u), first root the tree at u (which might be a leaf node).
We also define a coloring procedure for any rooted tree. First remove any existing color from all the nodes. Then select some nodes and apply the colorSubtree function on them. When colorSubtree is called on any node u, it colors the entire subtree of u, including u.
You need to color "exactly" floor(L / 2) of the leaves. So, for any root node u, you will get a set of nodes, S, such that applying colorSubtree on each of its elements will result in exactly floor(L / 2) the leaves to be colored.
Note that such a set always exist because one can always choose any of floor(L / 2) leaves that are not root and put them in S.
rootScore(u) is the minimum cardinality for such a set if u is the root of the tree. What is the minimum rootScore across all the nodes in T?
- First line contains N, the number of nodes in tree T.
- The next N-1 lines contain 2 space separated integers, u and v, each denoting that there is an edge between vertex u and vertex v.
OutputOutput a single integer, the answer to the problem.
- 1 ≤ N ≤ 3000
- 1 ≤ u, v ≤ N
Input: 3 2 1 1 3 Output: 1
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA|
Fetching successful submissions