Nhận xét: Với mọi bộ ba đỉnh $(i,j,k)$ ta luôn có $dist(i,j)+dist(j,k) \geq dist(i,k)$. Dấu bằng xảy ra khi một đỉnh nằm trên đường đi của hai đỉnh còn lại.

$N \leq 20$

Duyệt trâu $N \choose K$ cấu hình, với mỗi cấu hình dễ dàng kiểm tra trong $O(K^2)$. Có thể đặt cận khi kiểm tra để tăng tốc

$K=3$

Bài toán đưa về việc đếm bộ ba $(i,j,k)$ sao cho không tồn tại đường đi đơn đi qua ba đỉnh này. Ta có thể đưa về việc đếm phần bù. Đáp án là $N \choose 3$ $- \sum_{i=1}^{N} \sum_{j=i+1}^{N}(dist(i,j)-1)$. Dễ dàng tính tổng các cặp $dist(i,j)$ trong $O(N^2)$ hoặc $O(N)$

$N \leq 500$

Định nghĩa một tập đỉnh không có quan hệ tổ tiên - con cháu với nhau là không tồn tại LCA của 2 đỉnh bất kì trong tập.

Từ các nhận xét trên, suy ra các đỉnh được chọn sẽ gồm 2 trường hợp sau đây:

• Tập hợp không có các đỉnh nào có quan hệ tổ tiên - con cháu với nhau.
• Chọn đỉnh $u$, và chọn một tập các đỉnh không có quan hệ tổ tiên - con cháu trong cây con gốc $u$.

Gọi $dp(u,k)$ là số cách chọn $k$ đỉnh trong cây con gốc $u$ thoả mãn điều kiện trên

Với mỗi cây con gốc $u$ ta tính $dp$ như sau:

• Gọi $dpChild(i,j)$ là số cách chọn $j$ đỉnh trong các con trực tiếp thứ $1..i$ của cây con gốc $u$
• $dpChild(0,0)=1$
• $dpChild(i,j)=\sum_{x=0}^{j}(dpChild(i-1,j-x)*dp(v,x))$
• $dp(u,i)=dpChild(child_u,i)$ với $child_u$ là số con của $u$
• Làm như vậy thì sẽ bị bỏ xót trường hợp có chọn đỉnh $u$. Trường hợp có chọn đỉnh $u$ chỉ ảnh hưởng đến $dp(u,1)$ và $dp(u,k)$. Ta có $dp(u,1)+=1$ và $dp(u,K)+=\sum dp(v,K-1)$ với $v$ kề $u$

Độ phức tạp: $O(N\times K^2)$

$N \leq 5000$

Sử dụng trick số 7 trong blog: https://codeforces.com/blog/entry/100910 để giảm độ phức tạp về $O(N^2)$