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 <iostream>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 3e5 + 10;
const int base = 1e9 + 7;
int n, m, timer, tin[N], tout[N], depth[N], p[N], pr[N], up[N][25], col[N];
vector <pair <int, int> > e;
vector <int> g[N];
bool mk[N];
void dfs(int v, int pred = 0) {
tin[v] = timer++;
pr[v] = pred;
up[v][0] = pred;
for (int i = 1; i < 20; ++i)
up[v][i] = up[up[v][i - 1]][i - 1];
for (int to : g[v])
if (to != pred) {
depth[to] = depth[v] + 1;
dfs(to, v);
}
tout[v] = timer++;
}
void paint(int v, int cl) {
if (mk[v]) {
if (col[v] != cl) {
cout << 0;
exit(0);
}
return;
}
mk[v] = 1;
col[v] = cl;
for (int to : g[v])
paint(to, cl ^ 1);
}
int f(int x) { return (x == p[x]) ? x : p[x] = f(p[x]); }
void unite(int x, int y) { p[f(x)] = f(y); }
bool upper(int v, int u) { return (tin[v] < tin[u]) && (tout[v] > tout[u]); }
int _lca(int v, int u) {
if (upper(v, u))
return v;
if (upper(u, v))
return u;
for (int i = 19; i >= 0; --i)
if (!upper(up[v][i], u))
v = up[v][i];
return up[v][0];
}
void find(int v) {
if (!v)
return;
if (f(v) == f(pr[v])) {
find(pr[v]);
pr[v] = pr[pr[v]];
}
}
void path(int u, int v) {
find(v);
while (depth[u] < depth[pr[v]]) {
unite(v, pr[v]);
find(v = pr[v]);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n - 1; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(0);
for (int i = 0; i < n; ++i)
g[i].clear(), p[i] = i;
for (int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
if (x == y)
continue;
if (tin[x] > tin[y])
swap(x, y);
if (tout[x] > tout[y]) path(x, y);
else {
int lca = _lca(x, y);
path(lca, x);
path(lca, y);
e.push_back(make_pair(x, y));
}
}
for (auto a : e) {
int x = f(a.first);
int y = f(a.second);
if (x == y) {
cout << 0;
return 0;
}
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i < n; ++i)
if (!mk[i])
paint(i, 0);
for (auto a : e)
unite(a.first, a.second);
set <int> s;
s.clear();
for (int i = 1; i < n; ++i)
s.insert(f(i));
int ans = 1;
for (int i = 0; i < int(s.size()); ++i)
(ans <<= 1) %= base;
cout << ans;
}
# | 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... |
# | 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... |