[luogu] P4981 父子 Cayley定理

前言

https://www.luogu.com.cn/problem/P4981 我是来做最小生成树的QAQ(怎么下一题又是Cayley定理)

思路

看完题目不难发现

就是让我们求 n个节点的有根树 有多少个形态

已知Cayley定理是求无根树

所以对于每一个无根树 我们都有n种选根 方案

所以这题的公式就是: n n − 1   m o d   1 e 9 + 9 n^{n-1} \bmod 1e9+9 nn−1mod1e9+9

因为有t组 选择用qmi

CODE

#include 
using namespace std;
using ll = long long;
ll ans = 1;
const int mod  = 1e9+9;
int n;
int  qmi(ll a, ll b)
{
    a %= mod;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void solve()
{
    int n;
    cin>>n;
    cout