Eritrocit

Time limit: 1s Memory limit: 128MB Input: Output:

Se dă un arbore cu NN noduri, numerotate de la 11 la NN, în care fiecare nod are asociată o culoare. Fiecare culoare este reprezentată de un număr din mulțimea {1,2,,N}\{1, 2, \dots, N\}. Numim componentă o mulțime de noduri care formează o regiune conexă (subgraf conex nevid al arborelui) în arbore și pentru care oricare două noduri din mulțime au aceeași culoare. Această mulțime nu trebuie să fie neapărat maximală.

Cerință

Se cere numărul de moduri distincte de a împărți toate nodurile arborelui în cel mult KK componente disjuncte. De vreme ce acest număr poate să fie foarte mare, se cere restul său la împărțirea cu 109+910^9+9.

Două moduri, M1M_{1} și M2M_{2} se consideră distincte dacă există două noduri uu și vv (1u,vN1 \leq u, v \leq N) care fac parte din aceeași componentă în M1M_{1} și nu fac parte din aceeași componentă în M2M_{2}.

Date de intrare

Prima linie va conține numerele NN și KK. A doua linie va conține NN numere naturale nenule mai mici sau egale decât NN. Al ii-lea număr reprezintă culoarea celui de-al ii-lea nod.
Următoarele N1N-1 linii conțin fiecare câte o pereche de noduri (u,v)(u, v), semnificând că în arbore există muchie între nodurile uu și vv.

Date de ieșire

Se va afișa un singur număr, reprezentând numărul de moduri în care se poate împărți arborele în cel mult KK componente, modulo 109+910^9 + 9.

Restricții și precizări

  • 1KN200 0001 \leq K \leq N \leq 200 \ 000;
  • 1u,vN1 \leq u, v \leq N;
  • Pentru 99 puncte, 1N151 \leq N \leq 15, 1K41 \leq K \leq 4;
  • Pentru alte 88 puncte, K=2K = 2;
  • Pentru alte 99 puncte, K=3K = 3;
  • Pentru alte 1919 de puncte, 1KN2001 \leq K \leq N \leq 200;
  • Pentru alte 1818 puncte, 1KN2 0001 \leq K \leq N \leq 2 \ 000;
  • Pentru restul de 3737 puncte, nu există restricții suplimentare.

Exemplu

stdin

5 3
1 1 1 1 2
2 4
1 2
5 4
3 4

stdout

4

Explicație

Putem împărți arborele în cel mult 33 componente în 44 moduri. Cele patru moduri sunt:

  • {5}\{5\} și {1,2,4,3}\{1, 2, 4, 3\};
  • {5}\{5\}, {1}\{1\} și {2,4,3}\{2, 4, 3\};
  • {5}\{5\}, {1,2}\{1, 2\} și {4,3}\{4, 3\};
  • {5}\{5\}, {1,2,4}\{1, 2, 4\} și {3}\{3\}.

Log in or sign up to be able to send submissions!