# SPOJ VOCV

## Summary

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.

Find the number of lights in an optimal lighting. Find the total number of such optimal lightings in the city.

## Explanation

Note

• 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.

## Implementations

c++
#include<iostream>
#include <list>

const int MOD = 10007;
const int MAXN = 100010;

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) {
int withNode = 1, withNodeCnt = 1, withoutNode = 0, withoutNodeCnt = 1;
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";
}
}

</syntaxhighlight>