This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 60,mod = 1e9 + 7;
vector<int> adj[N + 1];
vector<int> edge[N + 1][N + 1];
map<pair<int,int>,int> mp;
int pa[N + 1],cnt[N + 1];
void init() {
for(int i = 1;i <= N;i++) {
pa[i] = i;
cnt[i] = 1;
}
}
int find(int a) {
if(a == pa[a]) return a;
return pa[a] = find(pa[a]);
}
void unite(int a,int b) {
a = find(a);
b = find(b);
if(a == b) return;
if(cnt[a] < cnt[b]) swap(a,b);
pa[b] = a;
cnt[a] += cnt[b];
}
int cha[N + 1][N + 1],root;
void dfs(int s,int pa) {
cha[root][s] = pa;
for(auto u : adj[s]) {
if(u == pa) continue;
dfs(u,s);
}
}
int binpow(int x,int y) {
int res = 1,curr = x;
while(y > 0) {
if(y%2) {
res = (res * curr) % mod;
}
y /= 2;
curr = (curr * curr) % mod;
}
return res;
}
vector<pair<int,int>> st;
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int n,m,k;
cin>>n>>m>>k;
for(int i = 1;i < n;i++) {
int u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
mp[{u,v}] = i;
mp[{v,u}] = i;
}
for(int i = 1;i <= n;i++) {
root = i;
dfs(i,-1);
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
if(j == i) continue;
int tmp = j;
while(tmp != i) {
edge[i][j].push_back(mp[{tmp,cha[i][tmp]}]);
tmp = cha[i][tmp];
}
}
}
for(int i = 0;i < m;i++) {
int a,b;
cin>>a>>b;
st.push_back({a,b});
}
int sum = 0;
for(int i = 0;i < 1<<m;i++) {
int cnt = __builtin_popcountll(i);
init();
for(int j = 0;j < m;j++) {
if((i >> j)%2 == 0) continue;
int a = st[j].first,b = st[j].second;
for(auto u : edge[a][b]) {
unite(u,edge[a][b][0]);
}
}
int tmp = 0;
for(int i = 1;i <= n - 1;i++) {
tmp += (i == find(i));
}
if(cnt%2 == 1) {
sum = (mod + sum - binpow(k,tmp)) % mod;
} else {
sum = (sum + binpow(k,tmp)) % mod;
}
}
cout<<sum<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |