Submission

Score: 100

User: meme_boi2

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

Language: cpp

Time: 0.088 second

Submitted On: 2025-12-30 19:04:53

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<vector<int>> path(2e5+1);
int n , m,mod = 1e9+7, ans = 0;
int dfs(int u,int par){
    if(u <= n) return 1;
    int sz = 0;
    vector<int> mat;
    for(auto v: path[u]){
        if(v == par) continue;
        int tmp = dfs(v,u);
        sz += tmp;
        mat.push_back(tmp);
    }
    mat.push_back(n-sz);
    int dp[5][mat.size()];
    memset(dp,0,sizeof(dp));
    dp[1][0] = mat[0];
    for(int i = 0; i < mat.size(); i++){
        dp[1][i] = (dp[1][i-1] + mat[i])%mod;
        for(int j = 2; j <= 4; j++){
            dp[j][i] = (dp[j][i-1] + (dp[j-1][i-1]*mat[i])%mod)%mod;
        }
        
    }
    ans += dp[4][mat.size()-1];
    ans %= mod;
    return sz;
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n >> m;
    int q = n + m-1;
    while(q--){
        int u, v;
        cin >> u >> v;
        path[u].push_back(v);
        path[v].push_back(u);
        
    }
    dfs(n+1,-1);
    cout << ans;
}