Đường Đi Trong Khoảng Độ Dài · canuc80k6706

Cho một cây vô hướng gồm $n$ đỉnh. Mỗi cặp đỉnh phân biệt xác định đúng một đường đi đơn; độ dài của đường đi là số cạnh trên đường đó.

Hãy đếm số đường đi có độ dài thuộc đoạn đóng $[k_{1}, k_{2}]$ , tức là có ít nhất $k_{1}$ cạnh và nhiều nhất $k_{2}$ cạnh. Hai hướng giữa cùng một cặp đầu mút chỉ biểu diễn một đường đi, nên $(u, v)$ và $(v, u)$ không được tính riêng.

Input

Dòng đầu chứa ba số nguyên $n, k_{1}, k_{2}$ .
Mỗi trong $n - 1$ dòng tiếp theo chứa hai số nguyên $u, v$ , cho biết có một cạnh vô hướng nối hai đỉnh $u$ và $v$ .

Output

In một số nguyên duy nhất: số đường đi có độ dài thuộc đoạn đóng $[k_{1}, k_{2}]$ .
Kết quả có thể vượt giới hạn số nguyên $32$ -bit.

Constraints

$1 \leq k_{1} \leq k_{2} \leq n \leq 2 \cdot 1 0^{5}$ .
$1 \leq u, v \leq n$ .
$n - 1$ cạnh trong input tạo thành một cây.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 2000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Có $7$ cặp đỉnh cách nhau đúng $2$ cạnh và $6$ cặp cách nhau đúng $3$ cạnh. Vì cả hai độ dài đều thuộc đoạn $[2, 3]$ , đáp án là $7 + 6 = 13$ .

Quy các đường đi về một centroid: Xét centroid c của thành phần hiện tại. Với mỗi đỉnh u, gọi d(u) là khoảng cách từ c đến u.
Quy các đường đi về một centroid: Một đường đi qua c có hai đầu ở hai nhánh khác nhau sau khi bỏ c, hoặc có một đầu chính là c. Độ dài của nó bằng tổng hai độ sâu. Ta cần đếm các cặp có tổng thuộc đoạn đóng [k1,k2].
Quy các đường đi về một centroid: Thu danh sách độ sâu của toàn bộ thành phần, có cả độ sâu 0 của c. Số cặp trong danh sách có tổng thuộc đoạn được tính bằng bảng tần suất độ sâu và tổng tiền tố. Tuy nhiên, hai đỉnh thuộc cùng một nhánh không tạo đường đi qua c, nên ta trừ số cặp tương tự trong danh sách độ sâu của từng nhánh.
Quy các đường đi về một centroid: Các đỉnh có độ sâu lớn hơn k2 có thể bỏ qua, vì không thể ghép với một độ sâu không âm để tạo tổng không vượt k2.
Đếm cặp trong một danh sách độ sâu: Với freq[d] là số lần độ sâu d xuất hiện, ta tính số cặp có tổng không vượt một giá trị K. Dùng mảng tổng tiền tố để, với mỗi độ sâu d, biết có bao nhiêu phần tử có độ sâu không vượt K-d. Phép cộng này đếm cặp có thứ tự và có thể đếm một phần tử với chính nó; trừ các trường hợp tự ghép rồi chia đôi sẽ cho số cặp không thứ tự.
Đếm cặp trong một danh sách độ sâu: Số cặp có tổng trong [k1,k2] bằng:
Đếm cặp trong một danh sách độ sâu: pairs_at_most(k2) - pairs_at_most(k1-1).
Phân rã và chứng minh đúng: Sau khi đếm mọi đường đi qua c, xóa c và tiếp tục trên từng thành phần còn lại.
Phân rã và chứng minh đúng: Mọi cặp được cộng ở mức c nằm ở hai nhánh khác nhau hoặc có một đầu là c, nên đường đi thật sự qua c; điều kiện tổng độ sâu bảo đảm độ dài nằm đúng trong đoạn. Việc trừ từng nhánh loại toàn bộ cặp không đi qua c.
Phân rã và chứng minh đúng: Ngược lại, với một đường đi hợp lệ bất kỳ, xét centroid đầu tiên tách hai đầu mút sang hai thành phần khác nhau. Đường đó được đếm tại chính mức này. Trước đó hai đầu còn cùng thành phần, còn sau đó chúng không xuất hiện chung trong một bài toán con. Vì vậy mỗi đường đi hợp lệ được đếm đúng một lần.
Độ phức tạp: Mỗi đỉnh xuất hiện ở O(log n) mức phân rã. Việc đếm bằng tần suất tuyến tính theo tổng kích thước các danh sách ở mỗi mức.
Độ phức tạp: Thời gian O(n log n), bộ nhớ O(n).