Chơi lửa chùa (D div 1)
Xem PDFHôm nay đang chơi game "Lửa chùa" với những người bạn của mình.
"Lửa chùa" là một tựa game chiến thuật, tư duy, sinh tồn đỉnh cao, không phân biệt cày chay và nạp vip, nơi mà những người bạn có những thời gian vui vẻ với nhau. Vì thấy tựa game này rất hay nên chơi suốt ngày, quên ăn quên ngủ. Lần này đang trải nghiệm chế độ mới của tựa game mang tên "Sơn tăng dame". Cụ thể trong chế độ này sẽ có \(n\) ngôi nhà được đánh số từ \(1\) đến \(n\), có \(n-1\) đường đi hai chiều nối \(2\) ngôi nhà với nhau ( đảm bảo tạo thành cây ), trong đó sẽ có \(m\) ngôi nhà đặc biệt được sơn. Để chiến thắng thì người chơi cần xóa một số ngôi nhà không được sơn ( không được xóa nhà được sơn ) sao cho không có \(2\) ngôi nhà được sơn nào có thể đi đến với nhau.
Bây giờ phân vân không biết phải xóa ít nhất bao nhiêu ngôi nhà không được sơn để có thể chiến thắng, hãy giúp cậu ấy nhé !
Input
- Dòng đầu tiên là hai số nguyên dương \(n,m\).
- \(n-1\) dòng tiếp theo mỗi dòng là \(2\) số \(u,v\) biểu thị có đường đi nối \(2\) ngôi nhà này.
- Dòng cuối cùng là dãy \(C_1,C_2,...,C_m\) biểu thị các ngôi nhà được sơn.
Output
- Gồm một số nguyên duy nhất là kết quả, nếu không tồn tại cách xóa thỏa mãn thì in ra \(-1\).
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(m \le n \le 20\)
- Subtask \(2\) (\(20\%\) số điểm): \(m \le n \le 1000\)
- Subtask \(3\) (\(60\%\) số điểm): \(m \le n \le 5*10^5\)
Example
Test 1
Input
10 4
1 3
1 6
5 10
3 5
5 9
6 7
8 6
2 4
4 6
1 2 9 10Output
2Note
Giải thích: Xóa các ngôi nhà \(4,5\).
Bình luận
zì v trùi mới nghe có bài này lun ớ
Phi Phai !!!!!!!!!!!
skibidi dom dom yes yes
fai fai đồng đội em :))
"Sơn tăng dame"
:v
burh :))
Small.Thưa thầy là em muốn đóng góp thêm test được không ạ? Em thấy "một số" code có thể chết test này nhưng hình như trong bộ test của mình không có. Em cám ơn thầy!!
Khi nào có sol, em mong là có prove luôn cho em hiểu :((