Submission

Score: 100

User: Dormon

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

Language: cpp

Time: 0.079 second

Submitted On: 2025-06-22 21:15:41

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

int n, m, sz[200200];
i64 ans;
vector<int> vc[200200];
const int mod = 1e9 + 7;

void dfs1(int u, int pa){
  sz[u] = (u <= n);
  for(auto v:vc[u]){
    if(v == pa) continue;
    dfs1(v, u);
    sz[u] += sz[v];
  }
}

void dfs2(int u, int pa){
  if(u > n){
    vector<i64> pref(5, 0), a;
    pref[0] = 1ll;
    for(auto v:vc[u]){
      if(sz[v] > sz[u]) a.push_back((i64)(n - sz[u]));
      else a.push_back((i64)sz[v]);
    }
    for(auto x:a) for(int i = 4; i >= 1; --i) pref[i] = (pref[i] + pref[i - 1]*x)%mod;
    ans = (ans + pref[4])%mod;
  }
  for(auto v:vc[u]){
    if(v == pa) continue;
    dfs2(v, u);
  }
}

int main(){
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> m;
  for(int i = 0; i < n + m - 1; ++i){
    int u, v; cin >> u >> v;
    vc[u].push_back(v);
    vc[v].push_back(u);
  }
  dfs1(1, -1);
  dfs2(1, -1);
  cout << ans << '\n';
}