C. Хүндийн төвүүд

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Мод гэдэг нь холбоост цикл биш графыг хэлдэг билээ. Танд $n$ ширхэг оройгоос тогтох нэгэн мод өгөгдсөн гэж үзье. Хэрэв нэгэн оройг модноос салган авахад үүсэх холбоотой хоёр хэсэг тус бүрийн оройн тоо нь -оос хэтрэхгүй байвал уг оройг хүндийн төв гэж нэрлэх юм.

Танд $n$ орой бүхий мод өгөгдсөн бөгөөд та нэгээс олонгүй ирмэгийг сольж болох байв. Ирмэг солих гэдэг нь модноос нэг ирмэгийг салган авч (уг ирмэгээр холбогдож буй оройнуудыг устгахгүй) граф нь мод хэвээрээ байхаар шинэ ирмэг байрлуулах (шинэ оройнууд нэмэхгүй) үйлдэл юм. Тэгвэл та орой болгоны хувьд нэгээс олонгүй ирмэгийг солих замаар уг оройг хүндийн төв болгох боломжтой эсэхийг тодорхойлно уу.

Оролт

Оролтын эхний мөрөнд бүхэл тоо $n$ ($2 ≤ n ≤ 400 000$) өгөгдөх ба энэ нь модонд байх оройн тоог илэрхийлнэ. Дараагийн $n - 1$ мөрийн мөр болгонд $u_{i}$ and $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$) гэсэн хос оройн индексүүд өгөгдөх ба эдгээр нь харгалзах ирмэгийн оройнуудыг илэрхийлнэ.

Гаралт

$n$ ширхэг бүхэл тоо хэвлэх ба эдгээрийн $i$-дахь тоо нь хэрэв $i$-дахь орой нь нэгээс олонгүй ирмэгийг солих замаар хүндийн төв болж болох бол $1$-тэй тэнцүү байх ба бусад тохиолдолд $0$-тэй тэнцүү байх юм.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
3
1 2
2 3
Гаралт
1 1 1 
Оролт
5
1 2
1 3
1 4
1 5
Гаралт
1 0 0 0 0 

Тэмдэглэл

Эхний жишээнд орой болгон нь хүндийн төв болж чадах юм. Жишээлбэл $1$ гэсэн оройг хүндийн төв болгохын тулд бид $(2, 3)$ гэсэн ирмэгийг $(1, 3)$ гэсэн ирмэгээр солиход болно.

Сэтгэгдлүүдийг ачааллаж байна...