Bác VA có N đồng cỏ, được kết nối với nhau bởi
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
Dữ liệu:
- Dòng đầu tiên là số N (
) - 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. (
).
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.