PVHOI 2021 tree

#define task "tree"

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e6 + 5;
ll Pow(ll a, ll b, ll mod);
ll mod, p;

pair<ll, int> gt[N], rgt[N];

int n, k;
int cnt[N];
vector<int> adj[N];

void Read()
{
    cin >> n >> k >> p;
    for (int i = 1; i < n; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
}

ll C(int k, int n)
{
    if (k > n)
        return 0;
    if (gt[n].second + rgt[k].second + rgt[n - k].second > 0)
        return 0;
    return gt[n].first * rgt[k].first % mod * rgt[n - k].first % mod;
}

ll Cal(ll mods)
{
    mod = mods;
    rgt[0] = gt[0] = make_pair(1, 0);

    for (int i = 1; i <= n; ++i)
    {
        ll v = i;
        gt[i] = gt[i - 1];
        rgt[i] = rgt[i - 1];

        while (v % mod == 0)
        {
            v /= mod;
            ++gt[i].second;
            --rgt[i].second;
        }

        (gt[i].first *= v) %= mod;
        rgt[i].first = v;
    }
    for (int i = 1; i <= n; ++i)
        rgt[i].first = rgt[i + 1].first;

    rgt[n].first = Pow(gt[n].first, mod - 2, mod);
    for (int i = n - 1; i; --i)
        (rgt[i].first *= rgt[i + 1].first) %= mod;

    ll ans(0);

    function<void(int, int)> GetAns = [&](int v, int p)
    {
        (ans += C(k, n - 1)) %= mod;
        cnt[v] = 1;

        for (auto i : adj[v])
            if (i != p)
            {
                GetAns(i, v);
                cnt[v] += cnt[i];
                (ans -= C(k, cnt[i])) %= mod;
            }

        (ans -= C(k, n - cnt[v])) %= mod;
    };

    GetAns(1, -1);

    return (ans + mod) % mod;
}

void Sub_n()
{
    if (p == 1019972207)
        cout << Cal(p);
    else
    {
        ll a1 = Cal(19),
           a2 = Cal(127),
           a3 = Cal(467),
           a4 = Cal(907);

        ll m1 = p / 19,
           m2 = p / 127,
           m3 = p / 467,
           m4 = p / 907;

        cout << (a1 * m1 * Pow(m1, 17, 19) + a2 * m2 * Pow(m2, 125, 127) + a3 * m3 * Pow(m3, 465, 467) + a4 * m4 * Pow(m4, 905, 907)) % p;
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Sub_n();
}

ll Pow(ll a, ll b, ll mod)
{
    ll ans(1);
    for (; b > 0; b >>= 1)
    {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}