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

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/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;
}