Submission

Score: 0

User: erng

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

Language: cpp

Time: 0.006 second

Submitted On: 2026-03-19 18:15:23

#include <bits/stdc++.h>

using namespace std;

const int nx=1e5+5, mod=1e9+7;
int n, m, sz[nx], ans;
vector<int> adj[nx], cnt[nx];

void dfs(int u, int p)
{
    sz[u]=(u<=n);
    for (auto v : adj[u])
    {
        if (v==p) continue;
        dfs(v, u);
        if (sz[v]>0) cnt[u].push_back(sz[v]), sz[u]+=sz[v];
    }
    cnt[u].push_back(n-sz[u]);
}
int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1;i<n+m; i++)
    {
        int u, v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,1);
    for (int u=n+1; u<=n+m; u++)
    {
        int siz=cnt[u].size();
        if (siz>=4)
        {
            int dp[siz+1][5];
            for (int i=0; i<=siz; i++)
            {
                for (int j=0; j<5; j++)
                {
                    dp[i][j]=0;
                }
            }
            dp[0][0]=1;
            for (int i=1; i<=siz; 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]);
                }
            }
            ans+=dp[siz][4];
            ans%=mod;
        }
    }
    cout<<ans;
}