Łuk triumfalny XX OI

Cześć, mam problem z zadaniem http://main.edu.pl/pl/archive/oi/20/luk. Mój kod dostaje 30 pkt, reszta to WA, pomysł wygląda następująco: znajduję w drzewie najbardziej pesymistyczną ścieżkę (czyli poddrzewami w których jest najwięcej wierzchołków) i robię binsearcha po wyniku symulując przejście króla ową ścieżką. Dodam swój kod, może to nieco pomoże (tak wiem, że trochę bałagan się zrobił wyprzedzając komentarze). Prosze o pomoc, podzielenie się swoim pomysłem na rozwiązanie etc.
Pozdrawiam

#include <vector>
#include <iostream>
#include <queue>
using namespace std;
#define range 300001
vector < vector <int> > G;
vector < vector <int> > depth;
vector <int> path;

int direction[range], ilosc_dzieci[range], lvl[range];
bool visited[range];
int n, ostatni_poziom=0, max_tmp, kolejny_wierzcholek;

queue <int> Q;

int bfs(int capital)
{
    Q.push(capital);
    visited[capital]=true;

    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        int l = 0;

        for(int i=0; i<G[u].size(); i++)
        {
            int v = G[u][i];

            if(visited[v]==false)
            {
                Q.push(v);
                visited[v] = true;
                direction[v] = u;
                lvl[v] = lvl[u]+1;
                depth[lvl[v]].push_back(v);

                if(lvl[v] > ostatni_poziom)
                    ostatni_poziom = lvl[v];
            }
        }
    }

}

int dfs(int v)
{
    visited[v]=0; // zaznaczam ze odwiedzony
    max_tmp = 0;

    for(int i=0; i<G[v].size(); i++)
    {
        int u = G[v][i];

        if(ilosc_dzieci[u] > max_tmp && visited[u]==1)
        {
            max_tmp = ilosc_dzieci[u];
            kolejny_wierzcholek = u;
        }
    }

    if(visited[kolejny_wierzcholek]==1)
    {
        path.push_back(kolejny_wierzcholek);
        dfs(kolejny_wierzcholek);
    }
}

int main()
{
    ios_base::sync_with_stdio(0);

    int n, a, b;

    cin >> n;

    if(n==1)
    {
        cout << 0;
        return 0;
    }

    G.resize(n+1);
    depth.resize(n+1);

    for(int i=0; i<n-1; i++)
    {
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    bfs(1);

    for(int i=ostatni_poziom; i>=1; i--)
    {
        for(int j=0; j<depth[i].size(); j++)
        {
            int v = depth[i][j];

            ilosc_dzieci[direction[v]]++;
            ilosc_dzieci[direction[v]]+=ilosc_dzieci[v];
        }
    }

    // wyznaczam sciezke pesymistyczna

    path.push_back(1);
    dfs(1);

    vector<int> finish;

    finish.push_back(G[1].size());

    for(int i=1; i<path.size(); i++)
        finish.push_back(G[path[i]].size()-1);

    int pocz=1, kon=range, out=range;

    for(int i=0; i<path.size(); i++)
        cout << path[i] << " ";
        cout << endl;

    for(int i=0; i<finish.size(); i++)
        cout << finish[i] << " ";
        cout << endl;

    while(pocz!=kon)
    {
            int robotnicy=(pocz+kon)/2;
            int ile_razy=0, suma=0, tmp, f=0, ilosc_krokow=0;

            for(int i=0; i<finish.size(); i++)
            {
                tmp = finish[i];

                if(suma-tmp<0)
                {
                    while(suma-tmp<0)
                    {
                        suma+=robotnicy;
                        ile_razy++;
                    }

                    //cout << suma << " * " << ile_razy << endl;

                }



                suma-=tmp;

                ilosc_krokow++;

                if(ilosc_krokow < ile_razy)
                {
                    f=1;
                    break;
                }
            }


            cout << endl << robotnicy << " " << ilosc_krokow<< " " << ile_razy << " " << f << endl;

            if(ile_razy <= ilosc_krokow && f==0)
            {
                out=min(out, robotnicy);

                if(robotnicy==pocz || robotnicy==kon)
                    break;

                kon=robotnicy;
            }
            else
            {
                if(robotnicy==pocz || robotnicy==kon)
                    break;

                pocz=robotnicy;
            }

    }

    cout << out;

}

Na main.edu.pl masz tą zaletę, że do każdego zadania możesz pobrać testy. Pobierz do tego zadania, sprawdź jakie testy Ci nie działają i debuguj (np. weź najkrótszy, który Ci nie działa).

@JumpSmerf Dzięki za odpowiedź, pierwsze co zrobiłem to to co napisałeś, niestety dostaje WA na testach gdzie drzewo ma >1000 wierzchołków czego nie jestem w stanie rozrysować czy sprawdzić ręcznie, sprawdziłem najbardziej pesymistyczną ścieżkę (nic więcej na większych testach nie jestem w stanie sprawdzić) i wyszło mi, że moja odpowiedź jest poprawna, a nie jest jak się okazuje.

Zrobiłeś BFS-a, to był dobry krok.
Nie wgłębiałem się w kod, ale moja podpowiedź jest taka, że musisz jedynie odrobinę zmodyfikować normalnego BFS-a.
Zamiast normalnie dodawać wierzchołki do odwiedzenia i je usuwać, musisz zrobić dwie listy. Pierwsza określa wierzchołki do odwiedzenia w bieżącym kroku króla i oraz druga, która gromadzi wierzchołki do odwiedzenia w kolejnym kroku króla.
Iterując po pierwszej liście tworzysz następną, a po zakończeniu analizy kroku króla przypisujesz drugą do pierwszej, czyścisz drugą i analizujesz kolejny krok króla. Przy każdym kroku króla liczysz maksimum wielkości listy i to jest twój wynik.

Dzięki za odpowiedź,
@MarekR22
Albo nie do końca zrozumiałem albo takie podejście nie jest do końca optymalne, widać to np. dla testu:
10
1 2
1 3
1 4
3 5
5 6
6 7
6 8
6 9
6 10

1. Sztucznie zwiększamy stopień wierzchołka 0
2. Znajdujemy maksymalny stopień wierzchołka
3. Wypisujemy ten stopień pomniejszony o jeden.
   Ba nie potrzebny żaden BFS/DFS, niepotrzebny również żaden graf, wystarczy tablica stopni rozmiarem w ilość miast.

Chyba że źle zrozumiałem treść zadania

@_13th_Dragon też na początku myślałem, że o to chodzi, ale jednak nie. Potem myślałem, że chodzi o maksymalną szerokość drzewa (moje rozwiązanie), ale też nie.
Dla danych (zestaw 1a):

8
1 4
5 6
7 6
8 6
4 2
2 6
3 6

Prawidłowa odpowiedź to: 2, a nie 4 (patrz węzeł 6).
Czyli ekipy co dzień, robią tyle łuków ile jest ekip, chyba, się skończą miasta i trzeba optymalnie ich wykorzystać.

Przeszukujemy drzewo BFSem jakkolwiek. Dla każdej ścieżki obliczamy liczbę wszystkich łuków które musielibyśmy mieć zbudowane dotąd (= liczbie dotąd odwiedzonych nowych miast) przy założeniu, że król przechodził tą ścieżką, tj. suma stopni wszystkich wierzchołków na ścieżce. Dzielimy to przez długość ścieżki i zapisujemy w tablicy jako k[i]. Po przejrzeniu całego drzewa liczymy dla tablicy wartość ceil(max((k[i])). Złożoność: O(n).

Maksymalna szerokość drzewa może dać zbyt duży wynik, bo jeśli drzewo jest szerokie dopiero na samym dole, to na początku większość ekip nie miałaby nic do roboty. W rzeczywistości można budować łuki równocześnie na różnych głębokościach drzewa, w efekcie jak król już dojdzie do szerokiego miejsca w drzewie, większość łuków jest pobudowanych.

Skoro żadne poprzednie rozwiązanie nie jest poprawne ja przedstawię swoje ;)
W grafie robimy takiego dfs:

int il_r;
int Dfs(int akt){//zwraca ilość łuków która musi być wybudowana przed wejściem do tego miasta
			int il=1;
            bool used=0;
			v[akt].odw=1;
			for(vector<int>::iterator it=v[akt].kr.begin();it!=v[akt].kr.end();it++)//iteruje po sasiadach wierzcholka
				if(v[*it].odw==0){
					if(!used)il-=il_r;
                     used=1;
					il+=Dfs(*it);
				}
			return max(1,il);//bo wierzchołek w wierzchołku w którym jestem, musi zostać wybudowany łuk zanim król tam wejdzie
}

Takim dfs'em sprawdzamy czy da się spełnić warunki zadania il_r robotnikami. Da się gdy Dfs(0)==1, bo w stolicy istnieje juz luk triumfalny. Wiedząc jak sprawdzać w złożoności o(n) robimy binarysearch po ilości robotników (jeśli da się spełnić x robotnikami, to da się również x+1). To rozwiązanie dostaje 100pkt ;P