Zadanie Bezpieczeństwo Letni Obóz treningowy przed EJOI, grafy. Bład w kodzie.

Question

Mam problem z takim zadaniem: https://sio2.mimuw.edu.pl/c/oij15-wiekuisty-oboz/p/bez/

Wydaje mi się, że wystarczy zliczyć liczbę liści, i wynik to (liczba_liści + 1) / 2, bo łączymy każde dwa liście. Dostaję 52pkt(podejrzewam, że tylko pierwszy wiersz wejścia wypisuję dobrze, bo pisze ograniczenie, że tylko za pierwszy wiersz dobry jest 50pkt), kompletnie nie wiem gdzie jest błąd, debuguję już chyba z godzinę i nie dowieżam co się dzieje. W wypisywaniu poprostu siłowo paruję każde dwa liście.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, a = 0, b = 0;
vector<int> ile_wchodzi;
vector<int> jakie_maja_stopien_jeden;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    if (n == 1)
    {
        cout << "0" << '\n';
        return 0;
    }
    ile_wchodzi.assign(n+1,0);
    for (int i = 0; i < n-1; ++i)
    {
        cin >> a >> b;
        ile_wchodzi[a]++;
        ile_wchodzi[b]++;
    }

    for (int i = 1; i <= n; ++i)
        if (ile_wchodzi[i] == 1)
            jakie_maja_stopien_jeden.push_back(i);

    cout << (jakie_maja_stopien_jeden.size() + 1) / 2 << '\n';
    if (jakie_maja_stopien_jeden.size() % 2 == 0)
    {
        for (int i = 0; i < jakie_maja_stopien_jeden.size(); i+=2)
            cout << jakie_maja_stopien_jeden[i] << ' ' << jakie_maja_stopien_jeden[i+1] << '\n';
    }
    else
    {
        for (int i = 0; i < jakie_maja_stopien_jeden.size() - 1; i+=2)
            cout << jakie_maja_stopien_jeden[i] << ' ' << jakie_maja_stopien_jeden[i+1] << '\n';
        cout << jakie_maja_stopien_jeden[0] << ' ' << jakie_maja_stopien_jeden[jakie_maja_stopien_jeden.size()-1] << '\n';
    }

    return 0;
}

 

Answer 1

Zobacz test:

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

Co jak połączysz 4 z 5 oraz 6 z 7. Czy to będzie dobrze?

Comments

złe, to jak to można zrobić?

---

Nie poddawaj się tak szybko :) Pomyśl jeszcze trochę nad tym

---

Narazie mam pomysł jedynie jak w O(N^2) to zrobić. Ma to coś wspólnego z dwóspójnymi składowymi / mostami / punktami artykulacji (wyczytałem kiedyś, że jest coś takiego, tylko jeszcze nwm co)?

---

Jak wygląda ten pomysł w O(N^2)? W drzewie praktycznie wszystko jest mostem, punktem artykulacji, więc chyba się nie przyda

---

Jak usuniemy jakąś krawędź, to drzewo dzięki się na dwa mniejsze drzewa. Mój pomysł był taki, że jeśli liczba liści w całym drzewie jest parzysta, to szukamy takiej krawedzi, że w obu drzewach jest tyle samo liści i losowo uzupełniamy, a jak nieparzysta to szukamy podziału, że w jednym po drzewie jest o jeden liść więcej.

---

Ale jak teraz o tym myślę, to już nie wiem czy to jest dobre, chyba się wywali....

---

Ja tak szczerze nie wiem jak to zrobić. Zrobiłem mały research i wygląda na to że to zadanie pojawiło się na BOI. Tu jest niby jakieś rozwiązanie 

---

Szkoda, że do tych zadań z tego obozu nie ma rozwiązań, zadania są epickie, ale brakuje jakieś książeczki / omówień.....

---

Dlatego lepiej robić trudne zadanka jeśli są do nich solvy. Te zadania z EJOI są całkiem trudne, na OI by się nadały bez problemu