Submission

Score: 100

User: KantaponZ

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

Language: cpp

Time: 0.090 second

Submitted On: 2025-06-28 00:30:03

#include <bits/stdc++.h>
using namespace std;

#define ll long long

// P.S. My code is mostly inspired by FastXFourier's solution, their editorials save my sanity level a lot ;) Thx FastXFourier

const int N = 1e5 + 5;
const int M = 1e5 + 5;
const int mod = 1e9 + 7;

ll n, m, ans, sz[N + M];

vector<ll> adj[N + M], cnt[N + M];

void dfs(int u, int pa) {
    sz[u] = (u <= n);
    for (auto v : adj[u]) {
        if (pa == v) continue;
        dfs(v, u);
        if (sz[v] > 0) {
            cnt[u].emplace_back(sz[v]);
            sz[u] += sz[v];
        }
    }
    cnt[u].emplace_back(n - sz[u]);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n + m - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    dfs(1, 1);
    for (int u = n + 1; u <= n + m; u++) {
        ll ct = cnt[u].size();
        if (ct < 4) continue;
        ll dp[ct + 1][5];
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        for (int i = 1; i <= ct; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= 4; j++) {
                dp[i][j] = dp[i - 1][j] + (dp[i - 1][j - 1] * cnt[u][i - 1]);
                dp[i][j] %= mod;
            }
        }
        ans = (ans + dp[ct][4]) % mod;       
    }
    cout << ans;
}