Zad algorytmika - Blokady

Question

Witam,

Mam takie o to zadanie:

Dawno, dawno temu był sobie kraj mlekiem i miodem płynacy z rozkoszami, jakich nikt nigdy nie zaznał, gdzie problemy NP-zupełne rozwiazywało sie w czasie liniowym. Kraj ten zwał sie Bajtocja. Bajtocja składa sie z N miast połaczonych siecia dwukierunkowych dróg, w taki sposób, ze miedzy kazdymi dwoma miastami mozna przejechac tylko na jeden sposób bez zawracania.
      Król Bajtazar, aby poprawic humor sobie i swoim poddanym postanowił odnowic najwieksza ilosc dróg w Bajtocji. Niestety, nie pomyslał o tym, ze aby odnowic droge, nalezy najpierw ja zamknac. Poddani oburzyli sie, ze siec dróg bedzie zamknieta. Król bojac sie o swoja popularnosc ogłosił, ze dla kazdego miasta zamknie maksymalnie jedna droge, która przechodzi przez to miasto. Jednoczesnie jednak chce dokonac renowacji najwiekszej liczby dróg. Pomóz mu!
      Napisz program, który: wczyta ilosc miast w Bajtocji oraz opis dróg miedzy miastami, wyznaczy maksymalna liczbe dróg, która mozna poddac naprawom i wypisze wynik na standardowe wyjscie.
WEJSCIE
      W pierwszym wierszu znajduje sie jedna liczba naturalna N , okreslajaca liczbe miast. W kolejnych  N − 1 wierszach znajduje sie opis sieci dróg w Bajtocji. Opis kazdej drogi składa sie z dwóch liczb naturalnych u i v, oddzielonych pojedynczym odstepem i okreslajacych numery miast, które połaczone sa dana droga.
      Miasta numerowane sa kolejnymi liczbami naturalnymi od 1 do N (włacznie).
WYJSCIE
Twój program powinien wypisac na wyjscie dokładnie jedna liczbe całkowita — maksymalna liczbe dróg, które zostana poddane naprawom.
OGRANICZENIA
1 <= N <= 200 000.
PRZYKŁAD
Wejscie

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

Wyjscie

4

 

Udalo mi sie dojsc tylko do tego, ze ten graf da sie przedstawic jako drzewo.

Z gory dziekuje za wszystkie odpowiedzi.

Answer 1

Zadanie wygląda na programowanie dynamiczne. Ukorzenimy drzewo w wierzchołku 1. Mamy takie stany:

dp[v][0] - maksymalna liczba dróg do naprawy w poddrzewie ukorzenionym w wierzchołku v, zakładając że nie remontujemy drogi między v a którymś z jego dzieci

dp[v][1] - tak samo jak wcześniej, ale zakładamy, że remontujemy jakąś drogę między v i którymś jego dzieckiem

Pozostało wymyślić jak liczyć dp

Answer 2

No da się przedstawić to za pomocą grafu

I jak mam być szczery to wynik nie jest zgodny z założeniem (opisem).

Król bojac sie o swoja popularnosc ogłosił, ze dla kazdego miasta zamknie maksymalnie jedna droge, która przechodzi przez to miasto.

Zwróć uwagę na to co pogrubiłem. Nie da się zamknąć tylko jednej drogi. 2,4 i 6 mają zamknięte po dwie drogi aby wynik wyniósł 4.

Comments

Zacznijmy od tego, ze graf na rysunku jest skierowany, a powinnien byc nieskierowany. Wynik jest zgody z zalozeniem, mozna usunac droge nr. 1 (1-2), 4 (3-7), 5 (4-5) i 7 (6-8), wtedy dla kazdego miasta zostala usunieta maksymalnie jedna droga polaczona z nim.

---

To że jest skierowany to efekt korzystania z narzędzia do generowania grafów 

Jeżeli weźmiemy pod uwagę pojedyncze drogi to ma to sens.