VOCV - Con-Junctions
The city of Y-O is a network of two-way streets and junctions with the following properties:
- There is no more than one street between each pair of junctions.
- Every junction is connected to every other junction either directly via a street or through other junctions by a unique path.
- When a light is placed at a junction, all the streets meeting at this junction are also lit.
A valid lighting is a set of junctions such that if lights were placed at these, all the streets would be lit. An optimal lighting is a valid lighting such that it contains the least number of junctions.
The task is divided into two subtasks:
- Find the number of lights in an optimal lighting.
- Find the total number of such optimal lightings in the city.
Input
- The first line of the input contains a positive integer t <= 20, denoting the number of test cases.
- The description of the test cases follows one after the other.
- Network Description:
- The first line of description of a network consists of a positive integer n <= 100010 denoting the number of junctions in the network.
- Each junction is numbered with a unique integer between 1 and n.
- The following n-1 lines contain a pair of integers u v (1 <= u,v <= n) separated by a single space denoting that there is a street between junction u and junction v.
Output
The output must consist of t lines, the kth line corresponding to the kth network; (1 <= k <= t). The kth line must contain two integers separated by a single space. The first integer on the kth line must be the number of junctions in an optimal lighting of network k. The second integer must be N%10007, which is the remainder left by the number of optimal lightings when divided by 10007.
Example
Input:
2
4
1 2
2 3
3 4
3
1 2
1 3
Output:
2 3
1 1
hide comments
thanos_tapras:
2020-06-05 18:43:02
Very nice variation of known problem!
|
|
lnxdx:
2019-10-04 15:25:35
AC in shit! |
|
kmkhan_014:
2018-05-14 22:33:19
understanding the bottom up appproach will help you in solving subtask 2. good luck! |
|
rahulpadhy:
2017-01-03 20:20:00
Awesome problem.. DFS with DP works nicely :)
|
|
Sumit Vohra:
2016-02-13 17:18:01
took some time, dP on tree :) |
|
xxbloodysantaxx:
2015-07-20 21:21:51
Writing the bottom up for this problem gives you real essence of DP :) |
|
Ankit Sultana:
2015-06-27 21:43:32
Note: Don't take mod for first integer in output |
|
paras meena:
2014-09-01 11:45:11
Really Nice Problem ;) |
Added by: | Kashyap KBR |
Date: | 2005-12-12 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NEM NICE NODEJS PERL6 SCM qobi ST VB.NET |