Masala #0680

Xotira 16 MB Vaqt 1000 ms
14

Daraxtni bo’yash #1

nn ta tugundan iborat ildizga ega binar daraxt berilgan (rooted binary tree). Ya’ni daraxtning har bir tugunini ko’pi bilan ikkita bolasi bo’lishi mumkin.
Berilgan daraxtda iloji boricha ko’p tugunlarni bo’yash kerakki, bo’yalganidan so’ng daraxt muvozanatlangan bo’lib qolsin.

Muvozanatlangan daraxt deb quyidagi shartni qanoatlantiruvchi daraxtga aytiladi:
- har bir ikkita bolasi bor uu tugun uchun, shu bolalarini xx va yy bilan belgilaydigan bo’lsak, ildizi xx da bo’lgan va ildizi yy da bo’lgan qism daraxtlardagi bo’yalgan tugunlar soni teng bo’lsin.

Masalan, quyidagi daraxt muvozanatlangan daraxtga misol bo’la oladi:

- 3-tugunni ikkala bolasidagi qism daraxtda 1 tadan bo’yalgan tugun bor.
- 1-tugunni ikkala bolasidagi qism daraxtda 2 tadan bo’yalgan tugun bor.
- 4-tugunni bolalari soni 1 ta bo’lgani sabab, uni e’tiborga olish shart emas.


Kiruvchi ma'lumotlar:

Birinchi qatorda tugunlar soni nn kiritiladi (1n105)(1 ≤ n ≤ 10^5). Ikkinchi qatorda daraxt qirralarini ifodalovchi n1n - 1 ta uu va vv ko’rinishidagi sonlar juftligi beriladi (1u,vn,uv)(1 ≤ u, v ≤ n, u \ne v). Daraxt ildizi doim 1-tugun bo’ladi.

1-subtask(9 ball): Har bir tugunning ko’pi bilan bitta bolasi bor, n100n ≤ 100
2-subtask(20 ball): n15n ≤ 15
3-subtask(31 ball): Har bir tugunning 0 ta yoki 2 ta bolasi bor n105n ≤ 10^5
4-subtask(40 ball): n105n ≤ 10^5


Chiquvchi ma'lumotlar:

Bitta butun son - bo’yash mumkin bo’lgan maksimal tugunlar sonini chiqaring.


Misollar
# input.txt output.txt
1
6
1 3
4 1
3 2
6 3
4 5
5
Izoh:

Birinchi misoldagi daraxt yuqoridagi rasmda keltirilgan. Faqat qo’shimchasiga 1-tugunni ham bo’yash imkoni bor, shuning uchun javob 5.