#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int MOD=1000000007;
int qexp(int b,int p){
int res=1;
while (p){
if (p&1) res=res*b%MOD;
b=b*b%MOD;
p>>=1;
}
return res;
}
int n,m,k;
vector<int> al[65];
vector<int> pos[15];
int pp[65];
int d[65];
void dfs(int i,int p){
pp[i]=p;
for (auto it:al[i]){
if (it==p) continue;
d[it]=d[i]+1;
dfs(it,i);
}
}
struct UFDS{
int p[65];
void reset(){
rep(x,0,65) p[x]=x;
}
int par(int i){
if (p[i]==i) return i;
else return p[i]=par(p[i]);
}
void unions(int i,int j){
i=par(i),j=par(j);
p[i]=j;
}
} ufds;
signed main(){
cin.tie(0);
cout.tie(0);
cin.sync_with_stdio(false);
cin>>n>>m>>k;
int a,b;
rep(x,1,n){
cin>>a>>b;
al[a].pub(b);
al[b].pub(a);
}
dfs(1,-1);
rep(x,0,m){
cin>>a>>b;
while (a!=b){
if (d[a]<d[b]) swap(a,b);
pos[x].pub(a);
a=pp[a];
}
}
//rep(x,0,m){
//for (auto it:pos[x]) cout<<it<<" "; cout<<endl;
//}
int ans=0;
rep(mask,0,1<<m){
ufds.reset();
rep(bit,0,m) if (mask&(1<<bit)){
for (auto it:pos[bit]) ufds.unions(pos[bit][0],it);
}
int cnt=0;
rep(x,2,n+1) if (ufds.p[x]==x) cnt++;
cnt=qexp(k,cnt);
if (__builtin_parity(mask)) ans=(ans-cnt+MOD)%MOD;
else ans=(ans+cnt)%MOD;
}
cout<<ans<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
276 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
2 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
324 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
3 ms |
212 KB |
Output is correct |
| 6 |
Correct |
4 ms |
336 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
328 KB |
Output is correct |
| 4 |
Correct |
1 ms |
328 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
1 ms |
276 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
2 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
324 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
0 ms |
212 KB |
Output is correct |
| 23 |
Correct |
0 ms |
212 KB |
Output is correct |
| 24 |
Correct |
3 ms |
212 KB |
Output is correct |
| 25 |
Correct |
4 ms |
336 KB |
Output is correct |
| 26 |
Correct |
1 ms |
212 KB |
Output is correct |
| 27 |
Correct |
12 ms |
320 KB |
Output is correct |
| 28 |
Correct |
1 ms |
328 KB |
Output is correct |
| 29 |
Correct |
1 ms |
212 KB |
Output is correct |
| 30 |
Correct |
12 ms |
340 KB |
Output is correct |
| 31 |
Correct |
3 ms |
332 KB |
Output is correct |
| 32 |
Correct |
1 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
212 KB |
Output is correct |
| 34 |
Correct |
1 ms |
212 KB |
Output is correct |
| 35 |
Correct |
6 ms |
212 KB |
Output is correct |
| 36 |
Correct |
24 ms |
212 KB |
Output is correct |
| 37 |
Correct |
11 ms |
340 KB |
Output is correct |
