Solutions of Subgraph

Select solution language

kien10i Created at 5 likes

Gọi dp[u] là số đồ thị con trong cây con gốc u và có chứa u gọi v là con của u ta có công thức quy hoạch động dp[u] = (dp[v1] + 1)* (dp[v2] + 1) * (dp[vk] + 1) Với + 1 ở đây là trường hợp không chọn đỉnh con vi đó Kết quả bài toán là tổng của các dp[i] với (1 <= i <= n) Code tham khảo : https://ideone.com/nsU6OQ :)))))))))

Narancia Created at 1 likes

- Gọi dp[u] là số lượng tập con nằm trong cây con gốc u mà tồn tại ít nhất 1 đỉnh là u. - Áp dụng tổ hợp thì dp[u] sẽ bằng tích của mọi (dp[v]+1) với v là con trực tiếp của u. - Một tập hợp chứa CÁC TẬP CON thỏa mãn điều kiện nằm trong dp[u] sẽ có dạng {{u}, v1, v2,..., vk} với k là số lượng con v của u. Với v1, v2,..., vk là các tập thỏa mãn vi (1<=i<=k) tức là dp[v] HỢP thêm tập rỗng {} tức là không chứa v như trong dp[v]. Giải thích: - Ta cố định đỉnh u, dễ dàng nhận thấy bài toán chuyển về việc đếm tổ hợp thông thường: + Cố định đỉnh u có (1 cách). + Các tập hợp trong dp[v1] hoặc không chọn tập con nào trong cây con gốc v1 có (dp[v1]+1) cách. + ... + Các tập hợp trong dp[vk] hoặc không chọn tập con nào trong cây con gốc vk (có dp[vk]+1) cách. Tổng hợp lại thì dp[u]=TÍCH(1 * (dp[v1]+1) * (dp[v2]+1) * ... * (dp[vk]+1)).