Submission

Score: 100

User: mydKN

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

Language: cpp

Time: 0.064 second

Submitted On: 2025-06-25 15:01:33

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")

using namespace std;

#define emb emplace_back
#define em emplace
#define pb push_back
#define ll long long

const ll maxn = 2e5 + 5;
const ll mod = 1e9 + 7;

ll n, m;
vector<ll> adj[maxn];
ll sub[maxn];
ll res;
ll arr[maxn];

ll dfs(ll u, ll p){
    if(u <= n) ++sub[u];
    for(auto v : adj[u]){
        if(v == p) continue;
        sub[u] += dfs(v, u);
    }
    return sub[u];
}

ll dfs2(ll u, ll p){
    ll cnt = 0, qs[5] = {};
    qs[0] = 1;
    if(u > n){
        // cout << u << " ";
        for(auto v : adj[u]){
            if(v == p) arr[cnt++] = n - sub[u];
            else arr[cnt++] = sub[v];
            // cout << arr[cnt-1] << " ";
        }
        // cout << "\n";
        for(ll i=0;i<cnt;++i){
            for(ll j=4;j>0;--j){
                qs[j] = (qs[j] + (qs[j-1] * arr[i]) % mod) % mod;
            }
        }
    }
    for(auto v : adj[u]){
        if(v == p) continue;
        qs[4] = (qs[4] + dfs2(v, u)) % mod;
    }
    // cout << u << " " << qs[4] << "\n";
    return qs[4];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for(ll i=0;i<n+m-1;++i){
        ll u, v;
        cin >> u >> v;
        adj[u].emb(v);
        adj[v].emb(u);
    }
    dfs(1, -1);
    // for(int i=1;i<=n+m;++i) cout << sub[i] << " ";
    cout << dfs2(1, -1);
}

/*
6 3
1 7
2 7
3 7
4 8
5 9
6 9
7 8
8 9

9 4
1 10
2 10
3 10
4 10
5 11
6 11
7 12
8 13
9 13
10 12
12 11
12 13
*/