Untitled
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