Submission

Score: 100

User: navysrimuang

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

Language: cpp

Time: 0.078 second

Submitted On: 2026-04-23 17:45:51

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
#define int long long
int n,m;
vector<vector<pair<int,int>>> adj;
vector<int> sub;
void dfs(int u, int p){
    sub[u] = (u <= n ? 1 : 0);
    for(auto [t,v] : adj[u]){
        if(v == p) continue;
        dfs(v,u);
        sub[u] += sub[v];
    }

}


int32_t main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    adj.resize(n+m+1);
    sub.resize(n+m+1,0);
    for(int i = 0;i<n+m-1;i++){
        int a,b;
        cin >> a >> b;
        if(i < n){
            adj[a].push_back({0,b});
            adj[b].push_back({0,a});
        }else{
            adj[a].push_back({1,b});
            adj[b].push_back({1,a});
        }
    }

    dfs(1,0);
    ll sum = 0;
    for(int i = n+1;i<=n+m;i++){
        if(adj[i].size() >= 4){
            vector<int> p;
            for(auto[t,x] : adj[i]){
                p.push_back((sub[x] > sub[i] ? (n-sub[i]) : sub[x]));
            }
            int k = p.size();

            // cout << "\n";
            // for(int x : p) cout << x << " ";
            // cout << "\n";
            vector<vector<int>> dp(k+2, vector<int>(4,0));

            for(int l = 0;l<4;l++){
                for(int j = 1;j<=k;j++){
                    if(l) dp[j][l] = dp[j-1][l-1]*p[j-1];
                    else dp[j][l] = p[j-1];
                    dp[j][l] += dp[j-1][l];
                    // cout << dp[l][j] << " ";
                }
                // cout << "\n";
            }

            sum += dp[k][3];
            sum %= MOD;

        }
    }
    cout << sum << "\n";
    // for(int i = 1;i<=n+m;i++) cout << sub[i] << " ";
    return 0;
}