Hợp nhất rừng cây và đường kính
Points
75
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho $N$ đỉnh rời rạc (ban đầu chưa có cạnh nào). Thực hiện $Q$ thao tác thuộc hai loại:
1 u v: nối đỉnh $u$ và $v$ bằng một cạnh độ dài $1$ (nếu $u$ và $v$ đã cùng thành phần liên thông thì bỏ qua).2 u: in ra đường kính hiện tại (số cạnh của đường đi đơn dài nhất) trong thành phần liên thông chứa đỉnh $u$.
Dữ liệu vào
Dòng đầu chứa hai số nguyên $N, Q$.
$Q$ dòng tiếp theo, mỗi dòng là một thao tác dạng 1 u v hoặc 2 u.
Dữ liệu ra
Với mỗi thao tác loại 2, in ra kết quả trên một dòng.
Ví dụ
| Input | Output |
|---|---|
| 5 6 1 1 2 2 1 1 2 3 1 4 5 2 3 2 4 |
1 2 1 |
Giới hạn
$1 \le N, Q \le 10^5$, $1 \le u, v \le N$.
Community Discussion