Submission

Score: 100

User: Trin1506

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

Language: cpp

Time: 0.097 second

Submitted On: 2026-04-25 14:08:58

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<vector<ll>> adj(200005);
vector<ll> cnt(200005,0);
vector<ll> parent(200005,0);
ll q;
void dfs(ll u,ll p){
   parent[u] = p;
   if(u<=q)cnt[u] = 1;
   for(auto x : adj[u]){
    if(x!=p){
        dfs(x,u);
        cnt[u]+=cnt[x];
    }
   }
}
int main(){
    ll n,m;
    const ll mod = 1e9+7;
    cin >> n >> m;
    q = n;
    for(ll i=0;i<n;i++){
        ll u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(ll i=0;i<m-1;i++){
        ll u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    vector<ll> dp(4);
    ll ans =0;
    for(ll i=n+1;i<=n+m;i++){
        if(adj[i].size()>=4){
        dp.assign(4,0);
        for(auto x : adj[i]){
            ll v = 0;
            if(x==parent[i]){
                v=(n-cnt[i])%mod;
            }
            else v = cnt[x]%mod;
            dp[3] = (dp[3]+(dp[2]*v)%mod)%mod;
            dp[2] = (dp[2]+(dp[1]*v)%mod)%mod;
            dp[1] = (dp[1]+(dp[0]*v)%mod)%mod;
            dp[0] =(dp[0]+v)%mod;
            }
            ans=(ans+dp[3])%mod;
        }
    }
    cout << ans;
}