#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME (1.0 * clock() / CLOCKS_PER_SEC)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 60 + 5;
const int oo = 1e9, mod = 1e9 + 7;
int n, m, k, parent[N], depth[N], path[N], uf[N], union_mask[N];
vector<int> adj[N];
int add(int a, int b) {
return (a + b) % mod;
}
int sub(int a, int b) {
return (a - b) % mod;
}
int mul(int a, int b) {
return (a * b) % mod;
}
long long binpow(long long a, long long b) {
a %= mod;
long long res = 1;
while (b > 0) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
void dfs(int node, int p = -1, int d = 0) {
parent[node] = p;
depth[node] = d;
for (int i : adj[node]) {
if (i != p) dfs(i, node, d + 1);
}
}
void mark_path(int idx, int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
for (; depth[u] > depth[v]; u = parent[u]) {
path[idx] |= (1LL << u);
}
for (; u != v; u = parent[u], v = parent[v]) {
path[idx] |= (1LL << v);
path[idx] |= (1LL << u);
}
}
int fnd(int a) {
return uf[a] = (uf[a] == a ? a : fnd(uf[a]));
}
void un(int a, int b) {
a = fnd(a);
b = fnd(b);
uf[a] = b;
union_mask[b] |= union_mask[a];
}
void reset_uf() {
for (int i = 0; i < m; i++) uf[i] = i;
for (int i = 0; i < m; i++) union_mask[i] = path[i];
}
int compute(int mask) {
reset_uf();
for (int i = 0; i < m; i++) {
if (!(mask & (1 << i))) continue;
for (int j = i + 1; j < m; j++) {
if (!(mask & (1 << j))) continue;
if (path[i] & path[j]) {
un(i, j);
}
}
}
int cnt = 0;
int not_on_paths = n - 1;
for (int i = 0; i < m; i++) {
if (!(mask & (1 << i))) continue;
if (i != uf[i]) continue;
cnt++;
not_on_paths -= __builtin_popcount(union_mask[i]);
}
return binpow(k, cnt + not_on_paths);
}
void process() {
cin >> n >> m >> k;
foru(i, 1, n - 1) {
int u, v; cin >> u >> v;
adj[u].pb(v); adj[v].pb(u);
}
dfs(1);
foru(i, 0, m - 1) {
int c, d; cin >> c >> d;
mark_path(i, c, d);
}
int res = 0;
foru(mask, 0, (1 << m) - 1) {
int popcorn = __builtin_popcount(mask);
if (popcorn % 2 == 0) {
res = add(res, compute(mask));
} else {
res = sub(res, compute(mask));
}
}
cout << res;
return;
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
//freopen(".inp", "r", stdin);
//freopen(".out", "w", stdout);
process();
cerr << "Time elapsed: " << __TIME << " s.\n";
return 0;
}
/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Keep calm and get VOI
Flow:
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
600 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
4 ms |
348 KB |
Output is correct |
| 6 |
Correct |
4 ms |
344 KB |
Output is correct |
| 7 |
Correct |
1 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
