Submission

Score: 100

User: njoop

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

Language: cpp

Time: 0.071 second

Submitted On: 2025-05-23 18:01:58

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define MAXN 200005
#define MOD (int)(1e9+7)
#define INF (int)1e17
#define enl '\n'
#define int long long
#define DB(code) cout<<'\t'<<code<<'\n';
#define SP <<' '<<
using namespace std;
int n,m,ans;
vector<int> tree[MAXN];
int cnt[MAXN],up[MAXN];
void dfs_cnt(int cur,int prv){
    if(cur<n) cnt[cur]++;
    for(auto v: tree[cur]) if(v!=prv){
        dfs_cnt(v,cur);
        cnt[cur]+=cnt[v];
    }
}
void dfs_calc(int cur,int prv){
    if(cur>=n){
        vector<int> num;
        num.pb(up[cur]);
        for(auto v: tree[cur]) if(v!=prv) num.pb(cnt[v]);
        int x=num.size();
        int dp[5][x+1];
        for(int i=0; i<=x; i++) dp[0][i]=1;
        for(int j=1; j<=4; j++) dp[j][0]=0;
        for(int j=1; j<=4; j++) for(int i=1; i<=x; i++) dp[j][i]=(dp[j-1][i-1]*num[i-1]%MOD+dp[j][i-1])%MOD;
        ans=(ans+dp[4][x])%MOD;
    }
    for(auto v: tree[cur]) if(v!=prv){
        up[v]=up[cur]+cnt[cur]-cnt[v];
        dfs_calc(v,cur);
    }
}
signed main(){
    cin.tie(0)->sync_with_stdio(false);
    int u,v;
    cin >> n >> m;
    for(int i=1; i<n+m; i++){
        cin >> u >> v;
        u--; v--;
        tree[u].pb(v);
        tree[v].pb(u);
    }
    dfs_cnt(0,0);
    dfs_calc(0,0);
    cout << ans;
    return 0;
}

/*

6 2
1 7
2 7
7 3
3 8
8 4
8 5
8 6

6 1
7 1
7 2
7 3
7 4
7 5
7 6

*/