#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+1;
const long long MOD = 1e9+7;
int n, m, d[N], mp[N], dsu[2*N];
vector<pair<int,int> > g[N], rem[N];
vector<int> par[N];
priority_queue<int, vector<int>, greater<int> > df[N];
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int tpu, int v, int tpv) {
u += n*tpu; v += n*tpv;
if((u = root(u)) == (v = root(v))) return;
if(dsu[u] > dsu[v]) swap(u, v);
dsu[u] += dsu[v];
dsu[v] = u;
}
void init_lca(int u, int p) {
for(auto v: g[u]) if(v.first != p) {
d[v.first] = d[u] + 1;
par[v.first].push_back(u);
for(int j = 0; 1 << j+1 <= d[v.first]; j++)
par[v.first].push_back(par[par[v.first][j]][j]);
init_lca(v.first, u);
}
}
int get_lca(int u, int v) {
if(d[v] > d[u]) swap(u, v);
if(d[u] > d[v]) for(int j = 0; 1 << j <= d[u] - d[v]; j++)
if(d[u] - d[v] >> j & 1) u = par[u][j];
if(u == v) return u;
for(int j = 31 - __builtin_clz(d[u]); j >= 0; j--) if(j < par[u].size() && par[u][j] != par[v][j]) {
u = par[u][j];
v = par[v][j];
}
return par[u][0];
}
int find_child(int u, int v) {
assert(d[v] > d[u]);
for(int j = 31 - __builtin_clz(d[v] - d[u] - 1); j >= 0; j--)
if(d[v] - d[u] - 1 >> j & 1) v = par[v][j];
return v;
}
void dfs(int u, int par, int pedge_id) {
for(auto v: g[u]) if(v.first != par){
dfs(v.first, u, v.second);
mp[v.first] = v.second;
if(!df[v.first].empty() && df[v.first].top() < d[u]) {
merge(pedge_id, 0, v.second, 0);
merge(pedge_id, 1, v.second, 1);
}
if(df[v.first].size() > df[u].size()) swap(df[u], df[v.first]);
while(!df[v.first].empty()) df[u].push(df[v.first].top()), df[v.first].pop();
}
for(auto p: rem[u]) if(p.first != u && p.second != u) {
int x = find_child(u, p.first), y = find_child(u, p.second);
merge(mp[x], 0, mp[y], 1);
merge(mp[x], 1, mp[y], 0);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
init_lca(1, -1);
for(int i = 0, u, v; i < m; i++) {
cin >> u >> v;
int lca = get_lca(u, v);
rem[lca].emplace_back(u, v);
df[u].push(d[lca]);
df[v].push(d[lca]);
}
fill(dsu+1, dsu+2*n, -1);
dfs(1, -1, -1);
for(int i = 1; i < n; i++) if(root(i) == root(n+i)) {
cout << 0;
return 0;
}
for(int i = 1; i < n; i++) merge(i, 0, i, 1);
vector<int> ccs;
for(int i = 1; i < n; i++) ccs.push_back(root(i));
sort(ccs.begin(), ccs.end());
ccs.resize(distance(ccs.begin(), unique(ccs.begin(), ccs.end())));
long long ans = 1, b = 2, e = ccs.size();
while(e) {
if(e & 1) ans = (ans * b) % MOD;
b = (b*b) % MOD;
e >>= 1;
}
cout << ans;
}
// check if there exists some in subtree v such that depth of lca < depth of u -> 0 0 1 1
// for all pairs which are lca at u, v do 0 1 1 0
Compilation message
usmjeri.cpp: In function 'void init_lca(int, int)':
usmjeri.cpp:24:24: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
for(int j = 0; 1 << j+1 <= d[v.first]; j++)
^
usmjeri.cpp: In function 'int get_lca(int, int)':
usmjeri.cpp:33:11: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
if(d[u] - d[v] >> j & 1) u = par[u][j];
^
usmjeri.cpp:35:58: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 31 - __builtin_clz(d[u]); j >= 0; j--) if(j < par[u].size() && par[u][j] != par[v][j]) {
^
usmjeri.cpp: In function 'int find_child(int, int)':
usmjeri.cpp:45:18: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
if(d[v] - d[u] - 1 >> j & 1) v = par[v][j];
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
356 ms |
68120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
716 ms |
128740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
37468 KB |
Output is correct |
| 2 |
Correct |
6 ms |
37600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
37468 KB |
Output is correct |
| 2 |
Correct |
9 ms |
37604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
38168 KB |
Output is correct |
| 2 |
Correct |
13 ms |
37732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
38188 KB |
Output is correct |
| 2 |
Correct |
9 ms |
37732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
803 ms |
91520 KB |
Output is correct |
| 2 |
Correct |
893 ms |
91696 KB |
Output is correct |
| 3 |
Correct |
493 ms |
65024 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
946 ms |
90676 KB |
Output is correct |
| 2 |
Correct |
929 ms |
90716 KB |
Output is correct |
| 3 |
Correct |
546 ms |
72268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
849 ms |
90752 KB |
Output is correct |
| 2 |
Correct |
856 ms |
92624 KB |
Output is correct |
| 3 |
Correct |
613 ms |
70008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
913 ms |
91632 KB |
Output is correct |
| 2 |
Correct |
826 ms |
92108 KB |
Output is correct |
| 3 |
Correct |
579 ms |
62620 KB |
Output is correct |
