Submission #13014638

---

Source Code Expand

#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<pii>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
 
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
 
// int power(int a,int n)
// {
//     a %= mod;
//     if(n == 1)return a;
//     if(n == 0)return 1;
//     if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
//     return power((a*a)%mod,n/2)%mod;
// }

// const int inf = (int) 1e18;
 
// int inverse(int x){
//     return power(x,mod-2)%mod;//little fermat....
// }

int n,lca[60][60],dp[(1<<20)+5][25];
vector<int>sub[60],mask(60),v1((1<<20)+5),v2((1<<20)+5);
vector<pii>adj[60],con(30),par(60);

void dfs(int x,int p){
    sub[x].pb(x);
    for(auto &y:adj[x]){
        if(y.f != p){
            par[y.f] = {x,y.se};
            dfs(y.f,x);
            for(auto &u:sub[y.f]){
                for(auto &v:sub[x]){
                    lca[u][v] = x;
                    lca[v][u] = x;
                }
            }
            for(auto &u:sub[y.f]){
                sub[x].pb(u);
            }
        }
    }
}

void solve(){
    int n;
    cin >> n;
    FOR(i,0,n-1){
        int u,v;
        cin >> u >> v;
        adj[u].pb({v,i});
        adj[v].pb({u,i});
    }
    par[1] = {1,-1};
    dfs(1,1);
    int m;
    cin >> m;
    FOR(i,0,m){
        cin >> con[i].f >> con[i].se;
        int l = lca[con[i].f][con[i].se];
        int u = con[i].f,v = con[i].se;
        while(u != l){
            mask[par[u].se] |= (1<<i);
            u = par[u].f;
        }
        while(v != l){
            mask[par[v].se] |= (1<<i);
            v = par[v].f;
        }
    }   
    n--;
    int half = n/2;
    FOR(i,0,(1<<half)){
        int tmp_mask = 0;
        FOR(j,0,half){
            if(i&(1<<j))tmp_mask |= mask[j];
        }
        v1[tmp_mask]++;
    }
    FOR(i,0,1<<(n-half)){
        int tmp_mask = 0;
        FOR(j,0,n-half){
            if(i&(1<<j))tmp_mask |= mask[half+j];
        }
        v2[tmp_mask]++;
    }
    FOR(i,0,(1<<20)){
        if(1&i)dp[i][0] = v2[i]+v2[i^1];
        else dp[i][0] = v2[i^1];
    }
    FOR(i,1,20){
        FOR(j,0,(1<<20)){
            dp[j][i] = dp[j^(1<<i)][i-1];   
            if(j&(1<<i))dp[j][i] += dp[j][i-1];
        }
    }
    long long ans = 0;
    FOR(i,0,(1<<20))ans += (long long )(v1[i]*dp[i][m-1]);
    cout << ans;
}

signed main()   
{
    showoff;
    int T = 1;
    //cin >> T;
    FOR(t,1,T+1){
       solve();
       cout << "\n";
    }
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...

Submission Info

Judge Result