Xaero is living in a country called Hackland. Hackland has the structure of a tree with N cities connected by N−1 bidirectional roads. Each city has an index between [1,N], and no two cities have the same index.
The president of Hackland thinks that traveling within a city is safe. However, traveling between cities, city A to a different city B, is not safe due to the poor lighting conditions in Hackland.
In order to ensure safety for the people traveling from one city to another, the president of Hackland decided to install some lights in the country. Each city can have, at most, 1 light installed in it. It is even possible that some cities already have lights installed. According to the president, traveling from one city A to a different city B is considered to be safe if there is at least 1 city on that path with a light installed.
Xaero knows that the Hackland budget is very limited. Therefore, he wants to help his president by telling him the minimum number of lights to be installed such that traveling from each city to every other city has become safe.
Input Format
First line of input contains an integer T denoting the number of test cases. First line of each test case contains a single integer N denoting the number of cities in the country called Hackland. Next line of each test case contains N space separated integers denoting the initial configuration of country i.e a '0' at ith position denotes that no light is installed in ith city whereas a '1' at ith position denotes that a light is already installed in the ith city. Next N−1 lines of each test case contains a pair of integers U and V denoting that there exists a bidirectional road between city U and city V.
MY Approach::
for this ques, I am using the approach that, I always pick the node with max deg. Lighten it(i.e. make its deg 0, and reduce the deg of its adjacent node by 1), I will keep doing this process until any node has deg greater than zero. For already lighten nodes, I am making their deg 0 and reduce the deg of their adjacent nodes by 1. But my ans is not correct for some test cases ?? Can any one please suggest what is wrong in my approach ??
I am sharing the code here ...
#include<bits/stdc++.h>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T, i, j, max, max_index, index, count, strt, end , N ;
bool flag ;
cin>> T ;
while(T--)
{
cin >> N ;
count = 0 ;
vector<vector<int>> tree ;
vector<int> init(N+1) ;
vector<int> deg(N+1) ;
fill(deg.begin(),deg.end(),0) ;
tree.resize(N+1) ;
for(i=1; i<=N; i++)
cin >> init[i] ;
for(i=0 ; i < N-1 ; i++)
{
cin>>strt>>end ;
tree[strt].push_back(end) ;
tree[end].push_back(strt) ;
deg[strt] = deg[strt] + 1 ;
deg[end] = deg[end] + 1 ;
}
for(i=1; i <=N ; i++)
{
if(init[i]==1)
{
deg[i] = 0 ;
for(j=0 ; j < tree[i].size(); j++)
{
index = tree[i][j] ;
deg[index] = deg[index] -1 ;
}
}
}
while(1){
flag = false ; //
for(i=1 ; i<= N ; i++)
{
if(deg[i] > 0){
flag = true ;
break ;
}
}
if(flag==false)
break ;
max = deg[1] ; //
max_index = 1; //
for(i=2; i <= N ;i++)
{
if(deg[i] > max)
{
max = deg[i] ;
max_index = i ;
}
}
// cout<<"max_index "<<max_index <<endl ;
count = count + 1 ; //
deg[max_index] = 0 ;
for(j=0; j < tree[max_index].size() ; j++)
{
index = tree[max_index][j] ;
deg[index] = deg[index]- 1 ; //
}
}
cout<<count<<endl ;
}
return 0;
}
Your approach is greedy while the real solution is based on DP(as your title suggests by the way). There are many examples where you could go wrong, but here is one I figured- you should take special care when multiple nodes have same degree and choose wisely:
1
5
00000
1 2
1 3
2 4
3 5
Please note that even if you output correct answer for this test case it would be due to pure luck - here you have three nodes of degree 2 and the best solution is to lighten only two of them - 2 and 3. Depending on the order you give equal nodes you may end up lighting node 1 which is wrong. Please note - there are many other cases where your solution would be wrong, this is simply the easiest I figured.