Subtask 1: \(1 \le n,k \le 8\)

Đệ quy quay lui để chọn màu cho n-1 cạnh, sau đó BFS từ mỗi đỉnh để kiểm tra.
Độ phức tạp \(O(k^{n-1}n^2)\)

Subtask 2: Cây nhị phân đầy đủ \(n = 2^x-1\)

Thử vẽ ra nháp đường đi độ dài 2 và độ dài 3 của cây nhị phân.

Lần lượt chọn màu cho cạnh của các nút từ gốc cho tới lá (theo độ sâu tăng dần).
Kí hiệu \(L(u), R(u)\) lần lượt là cạnh nối một nút u bất kì với con trái và con phải của nó.

\(L(u)\) và \(R(u)\) phải khác màu nhau. Vậy ta có \(k(k-1)\) cách chọn cho 2 cạnh của nút gốc.

Xét nút \(u\) khác gốc và tồn tại \(L(u)\) (cũng như \(R(u)\)). Kí hiệu \(p(v)\) là cha của nút \(v\) bất kì. Vậy \(L(u), R(u), L(p(u)), R(p(u))\), và cạnh nối \(p(p(u))\) tới \(p(u)\) phải đôi một khác màu (để đảm bảo mọi đường đi độ dài 2&3 kết thúc tại con của \(u\) có màu cầu vồng). Vì \(L(p), R(p),\) cạnh nối \(p(p(u))\) tới \(p(u)\) (nếu có) đã được xét màu từ trước nên có \((k-2)(k-3)\) hoặc \((k-3)(k-4)\) cách chọn màu cho \(L(u)\) và \(R(u)\).

Subtask 4:

Vì bậc mỗi nút không quá 3 nên cây sẽ có dạng cây nhị phân (có thể không đầy đủ). Việc suy luận công thức hoàn toàn tương tự như Subtask 2.

Subtask 6:

Ta tổng quát hóa ý tưởng của subtask 2 để tính. Thực hiện DFS để chọn màu cho các cạnh theo độ sâu tăng dần. Nếu nút \(u\) có cha, kí hiệu nó là \(p(u)\). Lúc này, việc chọn màu cho các cạnh nối nút \(u\) với con của nó cần thỏa mãn:

• Mọi cạnh nối \(u\) với con của nó phải khác màu với mọi cạnh nối với \(p(u)\).
• Các cạnh nối \(u\) với con của nó phải có màu khác nhau

Số cách chọn là chỉnh hợp chập \(c(u)\) của \(k-deg(p(u))\), trong đó \(c(u)\) là số lượng nút con của nút \(u\).

// Flower_On_Stone
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 505;
const int MOD = 1000000009;

int n, k;
vector<int> adj[MAX_N];
long long answer = 1;

long long A(int n, int k)
{
    long long resuft = 1;
    for (int i = n - k + 1; i <= n; i++)
    {
        resuft = resuft * i % MOD;
    }
    return resuft;
}

void dfs(int node, int parent)
{
    answer = answer * A(k - adj[parent].size(), parent == 0 ? adj[node].size() : adj[node].size() - 1) % MOD;
    for (auto &u : adj[node])
    {
        if (u != parent)
        {
            dfs(u, node);
        } 
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifdef Flower_On_Stone
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Flower_On_Stone
    cin >> n >> k;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    answer = 1;
    dfs(1, 0);
    cout << answer;
    return 0;
}