Submission

Score: 0

User: Trin1506

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

Language: cpp

Time: 0.013 second

Submitted On: 2026-04-25 14:00:52

#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;
    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++){
        dp.assign(4,0);
        if(adj[i].size()>=4){
        for(auto x : adj[i]){
            ll v = 0;
            if(x==parent[i]){
                v=n-cnt[i];
            }
            else v = cnt[x];
            dp[3] += dp[2]*v;
            dp[2] += dp[1]*v;
            dp[1] += dp[0]*v;
            dp[0]+=v;
            }
        }
        ans+=dp[3];
    }
    cout << ans;
}