жадный против динамического программирования

Ксаэро живет в стране под названием Хакленд. Хакленд имеет структуру дерева с N городами, соединенными N-1 двунаправленными дорогами. Каждый город имеет индекс между [1, N], и ни у одного города нет одинакового индекса.

Президент Хакленда считает, что путешествие по городу безопасно. Однако путешествие между городами, городом А, в другой город Б небезопасно из-за плохих условий освещения в Хакленде.

Чтобы обеспечить безопасность людей, путешествующих из одного города в другой, президент Хакленда решил установить в стране несколько фонарей. В каждом городе может быть установлено не более 1 светильника. Возможно даже, что в некоторых городах уже установлены светильники. По словам президента, путешествие из одного города А в другой город В считается безопасным, если на этом пути есть хотя бы один город с установленным освещением.

Xaero знает, что бюджет Hackland очень ограничен. Поэтому он хочет помочь своему президенту, сообщив ему минимальное количество устанавливаемых огней, чтобы путешествие из каждого города в любой другой стало безопасным.

Формат ввода

Первая строка ввода содержит целое число T, обозначающее количество тестовых случаев. Первая строка каждого теста содержит одно целое число N, обозначающее количество городов в стране под названием Хакленд. Следующая строка каждого контрольного примера содержит N целых чисел, разделенных пробелом, обозначающих начальную конфигурацию страны, то есть «0» в i-й позиции означает, что в i-м городе не установлен источник света, а «1» в i-й позиции означает, что источник уже установлен в I-й город. Следующие N-1 строки каждого теста содержат пару целых чисел U и V, обозначающих, что существует двусторонняя дорога между городом U и городом V.

МОЙ Подход ::

В этом задании я использую подход, который всегда выбирает узел с max deg. Осветлите его (то есть сделайте его градус 0 и уменьшите градус соседнего с ним узла на 1), я буду продолжать этот процесс, пока любой узел не будет иметь градус больше нуля. Для уже светлых узлов я делаю их градус 0 и уменьшаю градус их смежных узлов на 1. Но мой ответ неверен для некоторых тестовых случаев? Кто-нибудь может предложить, пожалуйста, что не так в моем подходе?

Я делюсь кодом здесь …

#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;
}