# Участник:Kachanov vv/CATER

Перейти к: навигация, поиск
```#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int max_n = 2505;
const int max_k = 95;
const int modulo = 10243;

class Solver {
public:
Solver(int N, int K) : N(N), K(K) {}

void init(){
for (int n = 1; n <= N - 1; n ++) {
int i, j;
cin >> i >> j;
edges[i].push_back(j);
edges[j].push_back(i);
}
for (int i = 1; i <= N; i ++) {
subtreeCount[i][0] = 1;
}
}
void dfs(int node, int parent) {
subtreeCount[node][1] = 1;
for (int i : edges[node]) {
if (i == parent) {
continue;
}
dfs(i, node);
multiply(subtreeCount[node], subtreeCount[i]);
}
result[node] = subtreeCount[node][K];
for (int i : edges[node]) {
if (i == parent) {
continue;
}
sum(result[node], result[i]);
}
}
void process() {
dfs(1, -1);
}
void sum(int &a, int b) {
a += b;
a %= modulo;
}
void multiply(int *a, int *b) {
vector<int> c(max_k);
copy(a, a + max_k, c.begin());
for (int i = 0; i < max_k; i ++) {
for (int j = 1; j < i; j ++) {
sum(a[i], b[j] * c[i - j]);
}
}
}
void dump() {
cout << result[1] << endl;
}

private:
int N, K;
int result[max_n], subtreeCount[max_n][max_k];
vector<int> edges[max_n];
};

int main() {
int N, K;
cin >> N >> K;
Solver solver(N, K);
solver.init();
solver.process();
solver.dump();

return 0;
}```