Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define fi first
- #define se second
- #define pb push_back
- #define pf push_front
- #define popb pop_back
- #define popf pop_front
- #define ins insert
- #define pq priority_queue
- #define minele min_element
- #define maxele max_element
- #define lb lower_bound //first pos >= val
- #define ub upper_bound // first pos > val
- #define cnt_bit __builtin_popcount
- #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("avx,avx2,fma")
- using namespace std;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef pair<int, int> pii;
- int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
- int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
- int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
- const ll oo = 1e18;
- const ll maxN = 1e6;
- /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
- void maximize(int &a, int b) {
- a = max(a, b);
- }
- void minimize(int &a, int b) {
- a = min(a, b);
- }
- ll MOD;
- const int N = 1e6 + 100;
- int n, k;
- int sz[N];
- int cnt[4][N], num[N];
- ll f[N], invf[N], fact[N], ans[N];
- vector<int> g[N];
- vector<int> b[N];
- ll Power(ll a, ll b, ll MOD) {
- if(b == 0) return 1;
- if(b == 1) return (a % MOD);
- ll T = Power(a, b / 2, MOD);
- if(b % 2) return (T * T % MOD * a % MOD);
- return (T * T % MOD);
- }
- int phi(int n) {
- int res = n;
- for (int i = 2; i * i <= n; ++i) {
- if (n % i == 0) {
- while (n % i == 0) {
- n /= i;
- }
- res -= res / i;
- }
- }
- if (n != 1) {
- res -= res / n;
- }
- return res;
- }
- void add(ll &x, ll y) {
- x = (x + y);
- if(x < 0) x += MOD;
- if(x >= MOD) x -= MOD;
- }
- void dfs(int u, int p) {
- sz[u] = 1;
- ans[u] = f[n - 1];
- for(auto v : g[u]) {
- if(v != p) {
- dfs(v, u);
- sz[u] += sz[v];
- add(ans[u], -f[sz[v]]);
- }
- }
- add(ans[u], -f[n - sz[u]]);
- }
- void solve() {
- //ans(u) = C(n - 1, k) - (v is son of u)C(chils(v), k) - C(n - child(u), k);
- //=> how to cal C(x, k)
- //C(x, k) = C(x - 1, k) * x / (x - k);
- //=> gcd(x, y) = 1 => x * c mod y = 1 (c = phi(y))
- cin >> n >> k >> MOD;
- for(int i = 1; i < n; i++) {
- int u, v;
- cin >> u >> v;
- g[u].pb(v);
- g[v].pb(u);
- }
- if(MOD == 1019972207) {
- fact[0] = 1;
- invf[0] = 1;
- for(int i = 1; i <= n; i++) {
- fact[i] = fact[i - 1] * i % MOD;
- invf[i] = Power(fact[i], MOD - 2, MOD);
- }
- for(int i = k; i <= n; i++) {
- f[i] = fact[i] * invf[k] % MOD * invf[i - k] % MOD;
- }
- } else {
- vector<int> prime = {19, 127, 467, 907};
- int euler = phi(MOD);
- fact[0] = 1;
- invf[0] = 1;
- for(int i = 1; i <= n; i++) num[i] = i;
- for(int i = 0; i < 4; i++) {
- for(int j = 1; j <= n; j++) {
- cnt[i][j] = cnt[i][j - 1];
- while(num[j] % prime[i] == 0) {
- num[j] /= prime[i];
- cnt[i][j]++;
- }
- }
- }
- for(int i = 1; i <= n; i++) {
- fact[i] = fact[i - 1] * num[i] % MOD;
- invf[i] = Power(fact[i], euler - 1, MOD);
- }
- for(int i = k; i <= n; i++) {
- f[i] = fact[i] * invf[k] % MOD * invf[i - k] % MOD;
- for(int j = 0; j < 4; j++) {
- int b = cnt[j][i] - cnt[j][k] - cnt[j][i - k];
- f[i] = f[i] * Power(prime[j], b, MOD) % MOD;
- }
- }
- }
- dfs(1, 0);
- ll res = 0;
- for(int i = 1; i <= n; i++) add(res, ans[i]);
- cout << res;
- }
- int main()
- {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- //online
- #endif
- int tc = 1, ddd = 0;
- // cin >> tc;
- while(tc--) {
- //ddd++;
- //cout << "Case #" << ddd << ": ";
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement