Submission

Score: 100

User: konthaina_TH

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

Language: cpp

Time: 0.058 second

Submitted On: 2026-09-23 23:44:17

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int mod = 1e9+7;
const int N = 2e5+5;
vector<int> graph[N];
vector<int> edge[N];
int val[N];
int n,m;

void dfs(int u,int p) {
    if (u <= n) {
        val[u] = 1;
    }
    for (int v : graph[u]) {
        if (v == p) continue;
        dfs(v,u);
        val[u] += val[v];
        edge[u].push_back(val[v]);
    }
}

void set_val(int u,int p) {
    if (u <= n) {
        return;
    }
    for (int v : graph[u]) {
        if (v == p or v <= n) continue;
        edge[v].push_back(n - val[v]);
        set_val(v,u);
    }
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i=0;i<n+m-1;i++) {
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    dfs(n+1,n+1);
    set_val(n+1,n+1);

    int ans = 0;
    for (int i = n+1;i<=n+m;i++) {
        if (edge[i].size() < 4) continue;
        int dp[5] = {0};
        for (int val : edge[i]) {
            dp[4] += dp[3] * val;
            dp[3] += dp[2] * val;
            dp[2] += dp[1] * val;
            dp[1] += val;
        }
        ans += dp[4] % mod;
    }
    cout << ans % mod << "\n";
    return 0;
}