Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.0 kB
6
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100005;
const int MOD = 1e9 + 7;

int n, k;
int fct[MAX_N], ifct[MAX_N];
vector<int> adj[MAX_N];
int sub[MAX_N];
int answer;

int inverse(int x) {
    if (x <= 1) {
        return 1;
    }

    return (MOD - MOD / x) * (long long)inverse(MOD % x) % MOD;
}

int choose(int n, int k) {
    if (n < 0 || k < 0 || n < k) {
        return 0;
    }

    if (n < MAX_N) {
        return fct[n] * (long long)ifct[n - k] % MOD * ifct[k] % MOD;
    }

    k = min(k, n - k);

    int res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (long long)(n - k + i) % MOD * inverse(i) % MOD;
    }

    return res;
}

void dfs(int node, int parent) {
    sub[node] = 1;
    for (auto u : adj[node]) {
        if (u != parent) {
            dfs(u, node);
            sub[node] += sub[u];
        }
    }

    int rem = sub[node] - 1;
    for (auto u : adj[node]) {
        if (u != parent) {
            answer = answer * (long long)choose(rem, sub[u]) % MOD;
            rem -= sub[u];
        }
        // cout << node << " " << u << " " << answer << "\n";
    }
}

int main() {
    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    freopen("scoring.inp", "r", stdin);
    freopen("scoring.out", "w", stdout);

    fct[0] = 1;
    for (int i = 1; i < MAX_N; i++) {
        fct[i] = fct[i - 1] * (long long)i % MOD;
    }

    ifct[MAX_N - 1] = inverse(fct[MAX_N - 1]);
    for (int i = MAX_N - 2; i >= 0; i--) {
        ifct[i] = ifct[i + 1] * (long long)(i + 1) % MOD;
    }

    cin >> n >> k;

    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    int root = -1;
    for (int u = 1; u <= n; u++) {
        int a;
        cin >> a;
        if (a == 1) {
            root = u;
        }
    }

    answer = choose(k, n);
    dfs(root, 0);

    cout << answer << '\n';

    return 0;
}
Leave a Comment