Mam takie zadanie: https://szkopul.edu.pl/problemset/problem/jgCcEjQu3kdpM4BmxA6GujfX/site/?key=statement
No i lecę sobie DFS i sprawdzam w każdym wierzchołku czy potrzebuje dodatkowych robotników, program daje błędny wynik dopiero w testach gdy n > 1000 więc trudno coś takiego debuggować. Program zwraca zbyt mały wynik np. potrzeba 6 robotników a mój program zwraca 5. Czy ktoś pomógłby mi znaleźć relatywnie małe testy dla których mój program daje błędne odpowiedzi?
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define FOR(x, y, z) for (int z = x; z < y; z++)
#define FORD(x, y, z) for (int z = x; z > y; z--)
const int MAXN = 3e5 + 7;
vector<vector<int>> graph(MAXN);
int min_need_workers = 0;
void dfs(int p, int idx, int deep, int prev_need_bows_to_build, int act_workers){
while((int)graph[idx].size()-(p!=-1) + prev_need_bows_to_build > act_workers * deep)
act_workers++;
for (auto child : graph[idx]){
if (child != p)
dfs(idx, child, deep+1, prev_need_bows_to_build+graph[idx].size()-(p!=-1), act_workers);
}
min_need_workers = max(min_need_workers, act_workers);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr); cout.tie(nullptr);
int n, a, b;
cin >> n;
FOR(0, n-1, i){
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
dfs(-1, 1, 1, 0, 0);
cout << min_need_workers << "\n";
return 0;
}