Submission

Score: 100

User: foldnut

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

Language: cpp

Time: 0.078 second

Submitted On: 2025-12-21 19:32:04

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 222222, MD = 1e9 + 7;
int n, m, ans, sz[N], a[N], dp[N][5];
vector<int> g[N];
void dfs1(int u, int p){
    if(u <= n){
        sz[u] = 1;
    }
    for(auto v : g[u]){
        if(v != p){
            dfs1(v, u);
            sz[u] += sz[v];
        }
    }
}
void dfs(int u, int p){
    if(u > n){
        int sm = 0, c = 0;
        for(auto v : g[u]){
            if(v == p) continue;
            a[++c] = sz[v];
            sm += sz[v];
        }
        a[++c] = n - sm;
        for(int i = 1;i<=c;i++){
            dp[i][1] = (dp[i - 1][1] + a[i]) % MD;
            dp[i][2] = (dp[i - 1][2] + (dp[i - 1][1] * a[i])) % MD;
            dp[i][3] = (dp[i - 1][3] + (dp[i - 1][2] * a[i])) % MD;
            dp[i][4] = (dp[i - 1][4] + (dp[i - 1][3] * a[i])) % MD;
        }
        ans = (ans + dp[c][4]) % MD;
    }
    for(auto v : g[u]){
        if(v != p){
            dfs(v, u);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0;i<n + m - 1;i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs1(1, -1);
    dfs(1, -1);
    cout << ans;
}