Submission

Score: 14

User: Dormon

Problemset: อพยพปลอดภัย (Quartet)

Language: cpp

Time: 1.094 second

Submitted On: 2025-05-24 19:23:06

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

int n, m, k;
vector<ll> fac, inv;
vector<int> deg, dp;
vector<vector<int>> adj;

template<typename T> ostream &operator << (ostream &out, vector<T> v){
    out << "[";
    for (auto e:v) out << e << ' ';
    out << "]";
    return out;
}

ll bin_pow(ll b, ll n){
    ll res = 1ll;
    while (n > 0ll){
        if (n & 1ll)
            res = (res * b) % mod;
        b = (b * b) % mod;
        n >>= 1ll;
    }
    return res;
}

void init(int n, int m){
    fac.assign(n + 1, 1ll);
    inv.assign(n + 1, 1ll);
    adj.resize(n + m + 1);
    deg.assign(n + m + 1, 0);
    for (int i = 2;i <= n;i++) fac[i] = (fac[i - 1] * (i + 0ll)) % mod;
    inv[n] = bin_pow(fac[n], mod - 2);
    for (int i = n - 1;i >= 2;i--) inv[i] = (inv[i + 1] * (i + 1ll)) % mod;
}

ll nCr(int n, int r){
    if (n < r) return 0ll;
    return (((fac[n] * inv[r]) % mod) * inv[n - r]) % mod;
}

bool home(int u){
    return 1 <= u && u <= n;
}

void dfs(int u, int p){
    if (dp[u] != -1) return ;
    dp[u] = home(u);
    for (auto v:adj[u]){
        if (v == p) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
}

ll combi(vector<int> v, int h){
    int sz = v.size() - 1;
    vector<ll> pf(sz);
    for (int i = 1;i <= sz;i++)
        pf[i] = pf[i - 1] + v[i];
    ll res = 0ll;

    auto mul = [&](ll a, ll b) -> ll {
        return (a * b) % mod;
    };

    for (int i = 1;i <= sz;i++){
        for (int j = i + 1;j <= sz;j++){
            res += mul(h, mul(v[i], mul(v[j], pf[sz] - pf[j])));
            res %= mod;
        }
    }
    
    for (int i = 1;i <= sz;i++){
        res += mul(nCr(h, 2), mul(v[i], pf[sz] - pf[i]));
        res %= mod;
    }

    res += mul(nCr(h, 3), pf[sz]);
    res %= mod;
    res += nCr(h, 4);
    res %= mod;

    for (int i = 1;i <= sz;i++){
        for (int j = i + 1;j <= sz;j++){
            for (int l = j + 1;l <= sz;l++){
                res += mul(v[i], mul(v[j], mul(v[l], pf[sz] - pf[l])));
                res %= mod;
            }
        }
    }
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    k = n + m;
    init(n, m);

    for (int i = 1;i < k;i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }

    bool can = false;

    for (int i = n + 1;i <= k;i++)
        if (deg[i] >= 4){
            can = true;
            break;
        }

    if (can == false){
        cout << "0\n";
        return 0;
    }

    ll ans = 0ll;

    for (int i = n + 1;i <= k;i++){
        if (deg[i] >= 4){
            dp.assign(k + 1, -1);
            dfs(i, -1);
            // cout << "dp " << i << " : " << dp << '\n';           
            int h = 0;
            vector<int> v = {0};
            for (auto next:adj[i]){
                if (dp[next] == 1) 
                    h++;
                else
                    v.push_back(dp[next]);
            }
            ans += combi(v, h);
            ans %= mod;
        }
    }
    cout << ans << '\n';
}