### Ý TƯỞNG
Để tính số đỉnh trong cây con gốc tại mỗi đỉnh của cây, ta có thể sử dụng **đệ quy DFS**. Ý tưởng như sau:
Với mỗi đỉnh i, ta muốn biết kích thước của **cây con gốc i (tính cả i)**.
Ta sử dụng **DFS** để duyệt tất cả các **đỉnh kề** với i.
Khi duyệt sang **đỉnh con** v, ta phải truyền tham số bao gồm cả **đỉnh cha** đã duyệt trước đó để tránh quay ngược lại đỉnh đã đi qua.
Khi gặp một **đỉnh lá** (tức là không có đỉnh kề nào khác ngoài đỉnh cha), ta trả về 1 **(cây con chỉ gồm chính nó)**.
Sau khi duyệt xong tất cả các đỉnh con, **tổng số đỉnh** thu được chính là **kích thước cây con của đỉnh đó**.
Kết quả được lưu vào **mảng cnt** để tránh tính lại.
### CODE THAM KHẢO
**Dưới đây là mã giả (pseudo-code) giải quyết vấn đề theo hướng trên, chỉ tham khảo khi thật sự cần thiết**:
```
Nhập n
Khởi tạo danh sách kề adj với n đỉnh
Khởi tạo mảng visited[] toàn bộ là false
Khởi tạo mảng cnt[] rỗng
// Đọc n - 1 cạnh của cây
For i từ 1 đến n - 1:
Nhập u, v
Thêm v vào adj[u]
Thêm u vào adj[v]
// Hàm đệ quy tính số đỉnh trong cây con gốc u
Hàm count_subtree(u, parent):
visited[u] = true
s = 1 // tính luôn đỉnh u
Với mỗi đỉnh v trong adj[u]:
Nếu v = parent:
Bỏ qua (tránh quay ngược lại cha)
Nếu v chưa được thăm:
s = s + count_subtree(v, u)
cnt[u] = s
Trả về s
// Chương trình chính
Gọi count_subtree(1, 1) để tính từ gốc 1
In cnt[1]
For i từ 2 đến n:
In cnt[i]
```
NotAndy
Created at
2 likes