Submission

Score: 18

User: kungarooo

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

Language: cpp

Time: 0.028 second

Submitted On: 2025-11-01 15:44:54

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const long long N=1e9+7,U=200001;
int n,m;
vector<vector<int>> adj(U);
ll dp=0,total_child[U]={};
ll dfs2(int node,int par){
    if(node<=n)return 1;
    int sz=0;
    for(auto i:adj[node]){
        if(i==par)continue;
        sz+=dfs2(i,node);
    }
    total_child[node]=sz;
    return 0;
}
ll dfs(int node,int par,ll tot){
    if(node<=n)return 1;
    vector<ll> arr;
    if(tot!=0)arr.push_back(tot);
    ll sz=0;
    tot+=total_child[node];
    for(auto i:adj[node]){
        if(i==par){
            continue;
        }
        ll tmpsz=dfs(i,node,tot);
        sz+=tmpsz;
        arr.push_back(tmpsz);
    }
    ll dd[5][arr.size()]={};
    dd[1][0]=arr[0];
    for(int i=1;i<arr.size();i++){
        dd[1][i]=dd[1][i-1]+arr[i];
        dd[1][i]%=N;
        for(int j=2;j<=4;j++){
            dd[j][i]=dd[j-1][i-1]*arr[i]+dd[j][i-1];
            dd[j][i]%=N;
        }
    }
    dp+=dd[4][arr.size()-1];
    dp%=N;
    //cout<<node<<" "<<dd[4][arr.size()-1]<<" "<<sz<<"::\n";
    return sz;
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(NULL);
    cin>>n>>m;
    for(int i=0;i<n+m-1;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs2(n+1,-1);
    dfs(n+1,-1,0);
    cout<<dp;
    return 0;
}