Submission

Score: 0

User: YoruoniVamp

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

Language: cpp

Time: 0.047 second

Submitted On: 2026-01-22 21:22:00

// YoruoniVamp - VTUBE
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int MOD = 1e9+7, N = 1e5+5, M = 1e5+5;
vector<vector<int>> adj, cnt;
int n, m, ans, city[N+M];
void dfs(int u, int prev) {
    city[u] = (u <= n);
    for(auto v: adj[u]) {
        if(v==prev) continue;
        dfs(v,u);
        if(city[v]>0) cnt[u].emplace_back(city[v]);
        city[u] += city[v];
    }cnt[u].emplace_back(n-city[u]);
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);cout.tie(0);
    // freopen("","r",stdin);
    // freopen("","w",stdout);
    cin >> n >> m;
    adj.resize(n+m+1);
    cnt.resize(n+m+1);
    for(int i = 1, u, v; i <= n+m-1; ++i) {
        cin >> u >> v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }dfs(1,1);
    // for(int i = n+1; i <= n+m; ++i) {
    //     for(auto j: cnt[i]) cout << j << ' ';
    //     cout << endl;
    // }
    for(int c = n+1; c <= n+m; c++) {
        // if(cnt[c].size()<4) continue;
        // Choose 0-4 ways
        int dp[5]{}; dp[0]=1;
        for(auto citycnt: cnt[c]) for(int j = 4; j >= 1; --j) dp[j] = (dp[j]+(dp[j-1]*citycnt)%MOD)%MOD;
        ans += dp[4];
    }cout << ans;
    return 0;
}