Постановка проблемы выглядит следующим образом:
Вам дано дерево из n узлов и целое число k. Каждый узел содержит целое число, хранящееся в нем. Вам необходимо удалить минимальное количество ребер (возможно, 0) из дерева таким образом, чтобы после удаления этих ребер сумма каждого отдельного дерева (сумма дерева была суммированием всех значений вершин этого дерева) была меньше или равно к.
Формат ввода
Первая строка: два целых числа через пробел и
Следующая строка: разделенные пробелом целые числа, где целое число обозначает значение, хранящееся в узле
Следующие строки: два разделенных пробелом целых числа, которые обозначают грань между узлом и
Выходной формат
Выведите целочисленный ответ на вопрос.
Ограничение
1 <= N <= 10 ^ 5 </p>
1 <= K <= 10 ^ 9 </p>
Пример ввода:
7 8
4 3 2 7 2 1 6
1 2
1 3
1 4
3 5
3 6
4 7
Пример вывода:
3
объяснения:
Удаляя ребра между узлами 1 и 3, ребро между узлами 1 и 4 и ребро между узлами 4 и 7. Мы можем получить необходимое условие при удалении минимум 3.
Я попробовал решение, в котором я решил эту проблему, используя подход dfs и, проверяя, больше ли сумма значения родительского узла + дочернего поддерева, чем k, затем удаляю этот край.
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int g[10004][10004];
int val[100005];
int ans=0;
int dfs(int u,int n,int k)
{
int s=val[u];
for(int i=0;i<n;i++)
{
if(g[u][i]==1)
{
int c = dfs(i,n,k);
if(c+s>k)
{
ans++;
}
s+=c;
}
}
return s;
}
int main()
{
int n,k,r;
cin>>n>>k;
for(int i = 0; i < n; i ++)
cin>>val[i];
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
g[i][j]=0;
}
}
for(int i = 0; i < n - 1; i ++)
{
int u,v;
cin>>u>>v;
if(i==0)
r=u;
g[u-1][v-1]=1;
}
int c = dfs(r-1,n,k);
cout<<ans;
return 0;
}
В некоторых тестовых случаях он работает нормально, но не в других, и я не могу найти такие тестовые примеры. Пожалуйста, помогите.