Ghép cây

View as PDF

Submit solution

Points: 0.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Sau khi chiến thắng Kỳ Tranh Tài và giành lấy được Bí Kíp Âm Nhạc, Gấu Trắng tìm hiểu được: một bản nhạc, biểu diễn cho một giai điệu, là một bảng dọc có kích thước ~6 \times 4~ gồm ~24~ số nguyên dương mang ý nghĩa là cao độ của các nốt nhạc.

Với đó, Gấu Trắng tiếp tục hành trình chinh phục Giai Điệu Ngàn Năm của mình. Chướng ngại vật đầu tiên của cậu chính là một con quái vật hung tợn trong rừng cây. Để đánh bại nó, cậu cần hợp nhất hai cành cây trong cánh rừng, tạo thành một chiếc đàn để đối phó với quái vật. Tuy nhiên, Gấu Trắng không biết cách tính điểm sức mạnh của việc hợp nhất hai cành cây này. Bạn hãy hỗ trợ Gấu Trắng giải bài toán sau nhé:

Cho 2 cây là ~A~ và ~B~ với mỗi cây có lần lượt là ~n~ và ~m~ đỉnh. Để tính sức mạnh của việc ghép hai cây, với mọi cặp đỉnh ~(i, j)~ (~i~ là một đỉnh trong ~A~, ~j~ là một đỉnh trong ~B~), ta nối hai đỉnh này lại. Việc nối này sẽ tạo ra một cây mới là ~T~, chi phí của cách ghép này chính là đường kính của cây ~T~ - được định nghĩa là khoảng cách xa nhất giữa hai đỉnh trong cây ~T~, khoảng cách được tính bằng số lượng cạnh nằm trên đường đi đơn giữa hai đỉnh đó.

Sức mạnh của hai cây ~A~ và ~B~ chính là tổng chi phí của mọi cách ghép hai cây đó. Nói cách khác, gọi ~f(x, y)~ là chi phí của việc nối đỉnh ~x~ của cây ~A~ với đỉnh ~y~ của cây ~B~ để tạo thành cây ~T~, hãy tính: $$\sum_{i=1}^{n} \sum_{j=1}^{m} f(i, j)$$

Input

  • Dòng đầu tiên gồm hai số nguyên dương ~n, m~ (~1 \leq n, n \leq 10^5~), lần lượt là số đỉnh của hai cây.

  • Dòng thứ ~i~ trong ~n - 1~ dòng tiếp theo gồm hai số nguyên dương ~x, y~ (~1 \leq x, y \leq n~), miêu tả một cạnh của cây ~A~.

  • Dòng thứ ~i~ trong ~m - 1~ dòng tiếp theo gồm hai số nguyên dương ~x, y~ (~1 \leq x, y \leq m~), miêu tả một cạnh của cây ~B~.

Output

Gồm một số nguyên dương duy nhất là đáp án của bài toán trên.

Scoring

  • Subtask ~1~ (~20\%~): ~n, m \leq 10^2~.

  • Subtask ~2~ (~40\%~): ~n, m \leq 10^3~.

  • Subtask ~3~ (~40\%~): ~n, m \leq 10^5~.

Sample Input 1

3 4
1 2
1 3
1 2
1 3
1 4

Sample Output 1

53

Notes

image

- Trên hình là 1 trong 12 cách ghép của test ví dụ 1, nối đỉnh ~1~ của ~A~ và đỉnh ~1~ của ~B~. Khoảng cách xa nhất giữa 2 đỉnh trong cách ghép này là ~3~, vậy nên đường kính là ~3~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.