Submission

Score: 100

User: Zonezonee

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

Language: cpp

Time: 0.055 second

Submitted On: 2026-04-10 17:43:39

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5+10, mod = 1e9+7;

int n, m;
vector<int> adj[N];
ll dp[5][N];
void dfs(int u, int p){
    dp[0][u] = 1;
    if(u <= n){
        dp[1][u] = 1;
        return;
    }
    int sum = 0;
    for(int v : adj[u]){
        if(v == p) continue;
        dfs(v, u);
        sum += dp[1][v];
    }
    for(int v : adj[u]){
        if(v == p) continue;
        for(int i = 4; i > 0; --i){
            dp[i][u] += (dp[i-1][u]*dp[1][v])%mod;
            dp[i][u] %= mod;
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    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(n+1, 0);
    ll ans = 0;
    for(int i = n+1; i <= n+m; ++i){
        if(i != n+1){
            for(int j = 4; j > 0; --j){
                dp[j][i] += (dp[j-1][i]*(n-dp[1][i]))%mod;
                dp[j][i] %= mod;
            }
        }
        ans = (ans+dp[4][i])%mod;
    }
    cout << ans << '\n';
}