Register | Login

Solutions of Path with length k

Select solution language All Tiếng Việt English Other

Write solution here.

---

minh2008    Created at    6 likes

Ý tưởng: sử dụng dfs từng đỉnh và dùng phương pháp quy hoạch động để tính toán. Gọi dp[u][j] là số lượng đường đi đơn có độ dài j từ đỉnh u đến một đỉnh con bất kì của u. -TH1: số lượng đường đi từ đỉnh u bất kì đến đỉnh v bất kì là con của đỉnh u có độ dài là k * =sum(dp[x][k-1]) (x là một đỉnh con trực tiếp của u). * note: nối 1 đoạn có độ dài k-1 bất kì với đỉnh u nếu giữa đoạn con đó và u có đường đi trực tiếp. -TH2: số lượng đường đi có độ dài là k được tạo bởi 2 nhánh của 1 đỉnh u bất kì: * =sum(dp[u][i]*dp[v][k-i-1]) (v là một đỉnh con trực tiếp của u) (1 <= i < k). Code tham khảo: https://ideone.com/HShhg2