#include <bits/stdc++.h>
/*
Things need to accomplish :
- Finding LCA : done
- Have time_in, time_out : done
- Decompose into components of demands from predec to ancestor : done
- Bipartiting
*/
using namespace std;
#define int long long
typedef pair <int, int> ii;
const int N = 3e5 + 5, MOD = 1e9 + 7, lg = 26;
int n, m, d[N], tin[N], tout[N], P[N][lg], x[N], y[N], dfsTime;
vector <int> adj[N];
bool inGraph[N]; // Create a new graph, with nodes are edges and the compenents, they has edges if both points to the same direction
void prepare(int u, int pre) {
tin[u] = ++dfsTime;
if (~pre) d[u] = d[pre] + 1;
for (int v : adj[u]) {
if (v == pre) continue;
P[v][0] = u;
prepare(v, u);
}
tout[u] = ++dfsTime;
}
int lca(int u, int v, ii &tw) {
bool swapped = false;
if (d[v] > d[u]) {
swapped = true;
swap(u, v);
}
for (int i = lg - 1; i >= 0; --i) if ((1 << i) <= d[u] - d[v])
u = P[u][i];
if (u == v) return u;
for (int i = lg - 1; i >= 0; --i) if ((1 << i) <= d[u] && P[u][i] != P[v][i])
u = P[u][i], v = P[v][i];
if (swapped) swap(u, v);
tw.first = u, tw.second = v;
return P[u][0];
}
struct dsu_t {
int n;
vector <int> lab;
dsu_t() {}
dsu_t(int _n) {
this -> n = _n;
lab.assign(n + 5, -1);
}
int root(int x) {
return lab[x] == -1 ? x : lab[x] = root(lab[x]);
}
void merge(int u, int v) {
int x = root(u), y = root(v);
if (x == y) return;
lab[y] = x;
}
};
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (int i = 1; i <= m; ++i) {
cin >> x[i] >> y[i];
}
prepare(1, -1);
for (int i = 1; i < lg; ++i) {
for (int u = 1; u <= n; ++u) {
P[u][i] = P[P[u][i - 1]][i - 1];
}
}
dsu_t one = dsu_t(n);
for (int i = 1; i <= m; ++i) {
int u = x[i], v = y[i];
if (tin[u] > tin[v]) swap(u, v);
if (!(tin[u] < tin[v] && tout[u] > tout[v])) continue;
u = one.root(u), v = one.root(v);
while (v != u) {
one.merge(P[v][0], v);
v = one.root(P[v][0]);
}
}
for (int i = 1; i <= n; ++i) {
// cerr << "At " << i << ": " << one.root(i) << endl;
if (one.root(i) == i) inGraph[i] = 1;
else inGraph[i] = 0;
}
dsu_t two = dsu_t(2 * n);
for (int i = 1; i <= m; ++i) {
int u = x[i], v = y[i];
if (tin[u] > tin[v]) swap(u, v);
if (tin[u] < tin[v] && tout[u] > tout[v]) continue;
ii d;
int uv = lca(u, v, d);
if (one.root(d.first) == one.root(d.second)) {
cout << 0 << endl;
return 0;
}
d.first = one.root(d.first), d.second = one.root(d.second);
two.merge(d.first, n + d.second);
two.merge(d.first + n, d.second);
u = one.root(u), v = one.root(v);
while (u != d.first) {
int pre = one.root(P[u][0]);
two.merge(pre, u);
two.merge(pre + n, u + n);
u = pre;
}
while (v != d.second) {
int pre = one.root(P[v][0]);
two.merge(pre, v);
two.merge(pre + n, v + n);
v = pre;
}
}
for (int i = 1; i <= n; ++i) if (inGraph[i] && two.root(i) == two.root(i + n)) {
cout << 0 << endl;
return 0;
}
int res = 1;
for (int i = 1; i <= 2 * n; ++i) if (inGraph[i > n ? i - n : i] && two.root(i) == i) {
inGraph[i > n ? i - n : i] = 0;
res = (res * 2) % MOD;
}
cout << res << endl;
return 0;
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:107:7: warning: unused variable 'uv' [-Wunused-variable]
107 | int uv = lca(u, v, d);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
126 ms |
46848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
315 ms |
118124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
9068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2103 ms |
106352 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
810 ms |
106348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
637 ms |
106628 KB |
Output is correct |
| 2 |
Correct |
1294 ms |
106732 KB |
Output is correct |
| 3 |
Correct |
323 ms |
73324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2065 ms |
106988 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
