Các lượt nộp

Danh sách bài

Báo lỗi

solution

Đề bài: [Giải thuật] Đếm cặp đỉnh có đường đi qua gốc

Cho cây $n$ đỉnh gốc tại $1$ . Đếm số cặp có thứ tự $(u, v)$ với $u \ne v$ sao cho đường đi đơn từ $u$ tới $v$ đi qua đỉnh gốc $1$ .

Gợi ý: tổng số cặp có thứ tự trừ đi các cặp nằm hoàn toàn trong cùng một nhánh con của gốc.

Định dạng đầu vào:
Dòng đầu: $n$ . $n-1$ dòng sau: các cạnh $u$ , $v$ .
Ràng buộc đầu vào:
$1 \le n \le 2\cdot10^5$ .
Định dạng đầu ra:
Một số nguyên: số cặp có thứ tự thỏa mãn.

Ví dụ:

Đầu vào:

3
1 2
1 3

Đầu ra:

6

Giải thích:

Gốc 1 có hai nhánh {2},{3}. Cặp qua gốc: (2,3) và (3,2); ngoài ra (1,2),(2,1),(1,3),(3,1) đều chứa gốc. Tổng 6.

Đang tải editor...