Dlaczego mój program daje złe wyniki? Zadanie Łuk Triumfalny OI (drzewa)

Question

Mam takie zadanie: https://szkopul.edu.pl/proble[...]mxA6GujfX/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;
}

Answer 1

W tego typu zadanich, gdzie operacje na liczbach mogą być duże zwykle problem leży w tym, że operujesz na int a nie np double, czy float. gdyż ich zakres jest większy.
Tym bardziej, że warunek rzutujesz na int, co może powodować ucinanie pewnych wartości

Comments

Niestety nie :(, wszystko mieści się w zakresach, a teraz  nawet znalazłem błędy test:

15
1 2
1 3
3 4
4 5
4 6
4 7
4 12
4 13
3 8
8 9
8 10
8 11
8 14
8 15