Bedao Regular Contest 02 - TOURIST

View as PDF

Submit solution


Points: 0.80 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C, C++, Java, Pascal, Python

Tình hình bệnh dịch đang diễn biến phức tạp ở đất nước Bedao, vì vậy chính phủ đã họp bàn để đưa ra kế hoạch tuyên truyển về cách phòng chống bệnh dịch trên khắp đất nước. Bản đồ đất nước Bedao gồm ~n~ địa điểm và ~n-1~ con đường. Mỗi con đường có đơn vị độ dài là ~1~. Chủ tịch thành phố cử ~1~ người ở thành phố ~A~ và ~1~ người ở thành phố ~B~ đi tuyên truyền. Biết rằng ~2~ người này sẽ đi thông qua các con đường để tuyên truyền với ràng buộc như sau:

  • ~2~ người xuất phát cùng lúc và đi liên tục với tốc độ bằng nhau
  • Không đi đến địa điểm cũng như con đường mà ~1~ trong ~2~ người đã đi qua .
  • Mọi lúc trong cuộc tuyên truyền ~2~ người phải ở ~2~ địa điểm khác nhau (~2~ người không cùng đến ~1~ chỗ)
  • Chiến dịch tuyên truyền chỉ dừng khi ~1~ trong ~2~ người không thể di chuyển được nữa.

Tìm phương án di chuyển sao cho số lượng địa điểm mà mỗi người đến gồm cả điểm bắt đầu là lớn nhất.

Input

  • Gồm ~1~ dòng chứa số nguyên ~n~ ~(1 \leq n \leq 2 \times 10^5)~ là số địa điểm trong đất nước cần phải đến
  • ~n-1~ dòng tiếp theo gồm ~2~ đỉnh ~u~ và ~v~ biểu thị con đường nối giữa địa điểm ~u~ và địa điểm ~v~ ~(1 \leq u,v \leq n)~
  • Dòng thứ ~n~ gồm ~2~ số nguyên ~A~ và ~B~ lần lượt là địa điểm xuất phát của cả ~2~ người ~(1 \leq A,B \leq n, A \neq B)~

Output

  • Một dòng duy nhất là số lượng địa điểm tối ưu mà mỗi người đến được.

Sample Input

6
1 2
2 3
3 4
4 5
5 6
4 5

Sample Output

2

Subtask

  • ~50\%~ số test có ~1 \leq n \leq 1000~
  • ~50\%~ số test còn lại không có điều kiện gì thêm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.