#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)x.size()
using ll = long long;
const int mod = 1e9+7;
const int LOG = 20;
vector<vector<int>> adj, up;
vector<vector<pair<int, int>>> edge_adj;
vector<pair<int, int>> ab;
vector<int> dist, min_anc, col;
void dfs(int u, int p = -1) {
if (p != -1) up[u][0] = p;
for (int v : adj[u]) {
if (v != p) {
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
}
int lca(int a, int b) {
if(dist[a] < dist[b]) {
swap(a, b);
}
int k = dist[a] - dist[b];
for(int j = LOG - 1; j >= 0; j--) {
if(k & (1 << j)) {
a = up[a][j];
}
}
if(a == b) {
return a;
}
for(int j = LOG - 1; j >= 0; j--) {
if(up[a][j] != up[b][j]) {
a = up[a][j];
b = up[b][j];
}
}
return up[a][0];
}
void dfs2(int u, int p = -1) {
for (int v : adj[u]) {
if (v != p) {
dfs2(v, u);
min_anc[u] = min(min_anc[u], min_anc[v]);
if (min_anc[v] < dist[u]) {
edge_adj[u].push_back({v, 0});
edge_adj[v].push_back({u, 0});
}
}
}
}
bool f = true;
void dfs3(int u, int c = 0) {
col[u] = c;
for (auto [v, e] : edge_adj[u]) {
if (col[v] == -1) {
dfs3(v, (e ? 1-c : c));
} else if (col[v] != (e ? 1-c : c)) {
f = false;
return;
}
}
}
ll binpow(ll a, ll b) {
a %= mod;
ll ret = 1;
while (b) {
if (b&1)
ret = (ret * a) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ret;
}
void solve(int tc) {
int n, m;
cin >> n >> m;
adj.resize(n); up.resize(n, vector<int>(LOG)); dist.resize(n); ab.resize(m); min_anc.resize(n); edge_adj.resize(n); col.resize(n, -1);
for (int i = 0; i < n-1; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto &[a, b] : ab) {
cin >> a >> b;
--a, --b;
}
dfs(0);
for (int i = 0; i < n; ++i) {
min_anc[i] = dist[i];
}
for (int l = 1; l < LOG; ++l) {
for (int u = 0; u < n; ++u) {
up[u][l] = up[up[u][l-1]][l-1];
}
}
for (auto [a, b] : ab) {
int u = lca(a, b);
if (a != u and b != u) {
edge_adj[a].push_back({b, 1});
edge_adj[b].push_back({a, 1});
}
min_anc[a] = min(min_anc[a], dist[u]);
min_anc[b] = min(min_anc[b], dist[u]);
}
dfs2(0);
int cc = 0;
for (int i = 0; i < n; ++i) {
if (col[i] == -1) {
dfs3(i);
if (!f) {
cout << "0\n";
return;
}
++cc;
}
}
cout << binpow(2, cc-1) << '\n';
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int tc = 1;
//cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
146 ms |
37848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
323 ms |
105840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
2 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
460 KB |
Output is correct |
| 2 |
Correct |
3 ms |
716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
535 ms |
76416 KB |
Output is correct |
| 2 |
Correct |
553 ms |
78140 KB |
Output is correct |
| 3 |
Correct |
303 ms |
50372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
567 ms |
80480 KB |
Output is correct |
| 2 |
Correct |
541 ms |
80360 KB |
Output is correct |
| 3 |
Correct |
418 ms |
54780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
537 ms |
80992 KB |
Output is correct |
| 2 |
Correct |
539 ms |
77212 KB |
Output is correct |
| 3 |
Correct |
381 ms |
55040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
575 ms |
81664 KB |
Output is correct |
| 2 |
Correct |
533 ms |
82116 KB |
Output is correct |
| 3 |
Correct |
327 ms |
50628 KB |
Output is correct |
