Đoạn đường
View as PDFBác VA có N đồng cỏ, được kết nối với nhau bởi ~N-1~ đoạn đường 2 chiều (có cấu trúc giống 1 cây). Lần này, vì quá già yếu, bác muốn chia ~N-1~ đoạn đường thành nhiều con đường 2 chiều dài hơn bằng cách ghép một số đoạn đường 2 chiều lại với nhau và giao cho những người làm thuê của mình quản lí. Để tìm người quản lí xứng đáng thay thế mình, bác quyết định mỗi con đường phải có cùng độ dài. Bác đang tự hỏi độ dài mỗi con đường bằng bao nhiêu.
Nhưng bác VA lại nghĩ ra 1 vấn đề khác, đó là với mỗi độ dài K thỏa mãn ~1<=K<=N-1~, liệu có thể chia ~N-1~ đoạn đường thành các con đường độ dài K hay không. Biết mỗi đoạn đường có độ dài là 1.
Dữ liệu:
- Dòng đầu tiên là số N (~2 <= N <= 100000~)
- N-1 dòng tiếp theo gồm 2 số u và v (u khác v) cho biết tồn tại đoạn đường từ u đến v. (~1<=a,b<=N~).
Kết quả:
Gồm N-1 số a[1],a[2],…,a[n-1] một cách liên tiếp. Trong đó a[i]=1 nếu tồn tại cách chia N-1 đoạn đường thành các con đường lớn có độ dài là i, a[i]=0 nếu không chia được.
Ví dụ :
INPUT
13
1 2
2 3
2 4
4 5
2 6
6 7
6 8
8 9
9 10
8 11
11 12
12 13
OUTPUT
111000000000
Giải thích:
Thỏa mãn để chia thành các con đường độ dài 1,2 hoặc 3. Với độ dài K=3 thì có thể chia thành các con đường gồm các đoạn đường nhỏ sau :
- (13−12−11−8)
- (10−9−8−6)
- (7−6−2−3)
- (5−4−2−1)
Ràng buộc:
Subtask1 : 30% số điểm có N<=1000
Subtask2: 70% số điểm không có rằng buộc gì thêm
Comments
This comment is hidden due to too much negative feedback. Show it anyway.