VOCV - Con-Junctions

https://www.spoj.com/problems/VOCV/

The city of Y-O is a network of two-way streets and junctions with the following properties:

1. There is no more than one street between each pair of junctions.
2. Every junction is connected to every other junction either directly via a street or through other junctions by a unique path.
3. 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:

1. Find the number of lights in an optimal lighting.
2. 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

http://www.algorithmist.com/index.php/SPOJ_VOCV

• the given graph is not cyclic.
• you either have to choose a vertex (or) you will definitely have to choose all the vertices connected to it.
• the optimal answer will be achieved by selecting an node or not selecting a node.

 using namespace std;
 
 int num_of_ways_optimal[MAXN];
 int num_of_ways_optimal_cnt[MAXN];
 int num_of_ways_with[MAXN];
 int num_of_ways_with_cnt[MAXN];
 
 void dfs(list<int> graph[], int x, int parent) {
   list<int> x_adj = graph[x];
   int withNode = 1, withNodeCnt = 1, withoutNode = 0, withoutNodeCnt = 1;
   for (std::list<int>::iterator y = x_adj.begin(); y != x_adj.end(); y++) {
     if(*y != parent) {
       dfs(graph, *y, x);
       withNode += num_of_ways_optimal[*y];
       withNodeCnt = (withNodeCnt * num_of_ways_optimal_cnt[*y]) % MOD;
     
       withoutNode += num_of_ways_with[*y];
       withoutNodeCnt = (withoutNodeCnt * num_of_ways_with_cnt[*y]) % MOD;
     }
   }
 
   num_of_ways_with[x] = withNode;
   num_of_ways_with_cnt[x] = withNodeCnt;
   
   if(withNode < withoutNode) {
     num_of_ways_optimal[x] = withNode;
     num_of_ways_optimal_cnt[x] = withNodeCnt;
   }
   else if(withNode > withoutNode) {
     num_of_ways_optimal[x] = withoutNode;
     num_of_ways_optimal_cnt[x] = withoutNodeCnt;
   }
   else{
     num_of_ways_optimal[x] = withNode;
     num_of_ways_optimal_cnt[x] = (withoutNodeCnt + withNodeCnt) % MOD;
   }
 }
 
 int main() {
   int tests;
   cin>>tests;
   for(int test = 0; test < tests; test++) {
     int n;
     cin>>n;
   
     list<int> graph[n+1];
     int a, b;
     for(int i=0; i < n-1; i++) {
       cin>>a>>b;
       graph[a].push_back(b);
       graph[b].push_back(a);
     }
   
     int root = 1;
     dfs(graph, root, -1);
     cout<<num_of_ways_optimal[root]<<" "<<num_of_ways_optimal_cnt[root]<<"\n";
   }
 }