Submission

Score: 100

User: exoworldgd

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

Language: cpp

Time: 0.056 second

Submitted On: 2025-11-09 00:16:11

#pragma GCC optimize("O5,unroll-loops,inline")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0), cout.tie(0)
#define int long long
using namespace std;
const int inf = LLONG_MAX, mod = 1e9+7, maxn = 2e5+5;
int deg[maxn],dp[5][maxn],sub[maxn];
vector<int> adj[maxn];
void dfs(int u, int p) {
    sub[u] = (u <= deg[0]) ? 1 : 0;
    for (int v : adj[u]) if (v^p) dfs(v,u), sub[u] += sub[v];
}
signed main(void) {
    exoworldgd;
    int n,m,x,y,ans=0;
    cin >> n >> m, deg[0]=n;
    for (int i = 0; i < n+m-1; i++) cin >> x >> y, adj[x].push_back(y), adj[y].push_back(x), deg[x]++, deg[y]++;
    dfs(n+1,-1);
    for (int i = n+1; i <= n+m; i++) {
        if (deg[i] < 4) continue;
        vector<int> v;
        for (int u : adj[i]) v.push_back(sub[u] < sub[i] ? sub[u] : sub[n+1] - sub[i]);
        int sz = v.size();
        if (sz < 4) continue;
        for (int k = 0; k < 5; k++) for (int j = 0; j <= sz; j++) dp[k][j] = 0;
        for (int j = 0; j <= sz; j++) dp[0][j] = 1;
        for (int j = sz-1; j >= 0; j--) for (int k = 1; k <= 4 && k <= sz-j; k++) dp[k][j] = dp[k][j+1], k == 1 ? dp[k][j] = (dp[k][j]+v[j])%mod : dp[k][j] = (dp[k][j]+(v[j]*dp[k-1][j+1])%mod)%mod;
        ans = (ans+dp[4][0])%mod;
    }
    cout << ans;
}