Submission

Score: 100

User: qweqwe

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

Language: cpp

Time: 0.101 second

Submitted On: 2026-03-25 23:41:58

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma comment(linker, "/stack:2000000")
#include <bits/stdc++.h>
#define qweqwe cin.tie(0)->sync_with_stdio(0)
using namespace std;
using ll = long long;
using pii = pair<ll,ll>;
using db = long double;

vector<vector<int>> graph(200067);
vector<ll> parent(200067);
unordered_set<int> spe; // SPE-CHANNNNN!!!!
vector<ll> dp(200067),sub(200067);
vector<bool> vis(200067);
const ll MOD = 1e9+7;

int dfs1(int x,int p){
	parent[x]=p;
	vis[x]=1;
	//if (x==1) parent[x]=1;
	sub[x]=0;
	if (!spe.count(x)) sub[x]=graph[x].size();
	// if (x<=n) sub[x]=1;
	for (int i:graph[x]){
		if (i==p || vis[i]) continue;
		vis[i]=1;
		sub[x] += dfs1(i,x);
	}
	return sub[x];
}

void dfs2(int x,int p){
	vis[x]=1;
	for (int y:graph[x]){
		if (y==p || vis[y]) continue;
		vis[y]=1;
		ll w = dp[x]-sub[y];
		dp[y]=sub[y]+w;
		dfs2(y,x);
	}
}

int main(){
	qweqwe;
	int n,m;cin >> n >> m;
	parent.resize(n+m+2);
	graph.resize(n+m+2);
	dp.resize(n+m+2);
	for (int i=0;i<n;i++){
		int st,en;
		cin >> st >> en;
		graph[st].push_back(en);
		graph[en].push_back(st);
	}
	for (int i=0;i<m-1;i++){
		int st,en;
		cin >> st >> en;
		graph[st].push_back(en);
		graph[en].push_back(st);
	}
	
	for (int i=n+1;i<=n+m;i++){
		spe.insert(i);
	}
	
	dfs1(1,-1);
	dp[1]=sub[1];
	fill(vis.begin(),vis.end(),0);
	dfs2(1,-1);
	
	/*
	for (int i=1;i<=n+m;i++){
		cout << dp[i] << " ";
	}cout << "\n";
	*/
	ll realsum=0;
	for (int i=n+1;i<=n+m;i++){
		int s = graph[i].size();
		if (s<4) continue;
		vector<ll> pf;
		
		for (int v:graph[i]){
			ll val=0;
			if (v==parent[i]){
				val=(dp[i]-sub[i]);
			}else{
				val=(sub[v]);
			}
			if (val<0) val+=MOD;
			pf.push_back(val);
		}
		
		/*
		for (int a=s;a>=3;a--){
			pf[a-1]=pf[a];
			for (int b=a+1;b<=s;b++){
				
				if (graph[i][b-1]==parent[i]){
					pb=dp[i]-sub[i];
				}else{
					pb=sub[graph[i][b-1]];
				}
				
				//cout << a << " " << b << '\n';
				pf[a-1]+=(pa*pb)%MOD;
				pf[a-1]%=MOD;
			}
			
			for (int j=2;j<=s;j++){
				cout << pf[j] << " ";
			}cout << '\n';
			
		}
		*/
		
		ll s1=0,s2=0,s3=0,s4=0;
		for (ll x:pf){
			s4=(s4+s3*x)%MOD;
			s3=(s3+s2*x)%MOD;
			s2=(s2+s1*x)%MOD;
			s1=(s1+x)%MOD;
		}
		
		realsum += (s4)%MOD;
		realsum%=MOD;
		
		/*
		for (int a=1;a<=s-2;a++){
			for (int b=a+1;b<=s-2;b++){
				int pa,pb;
				if (graph[i][a-1]==parent[i]){
					pa=dp[i]-sub[i];
				}else{
					pa=sub[graph[i][a-1]];
				}
				
				if (graph[i][b-1]==parent[i]){
					pb=dp[i]-sub[i];
				}else{
					pb=sub[graph[i][b-1]];
				}
				
				ll mul = (pa*pb)%MOD;
				
				//cout << mul << " " << (mul%MOD*pf[b]%MOD)%MOD << "\n";
				
				realsum += (mul%MOD*pf[b]%MOD)%MOD;
				realsum%=MOD;
			}
		}//cout << realsum << "\n";
		*/
	}
	cout << realsum%MOD;
	return 0;
}