//I love armpit fetish
#include <bits/stdc++.h>
using namespace std;
#define debug(x) {cerr << #x << " = " << x << '\n';}
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "data"
const int MAX_N = 300002;
const int MOD = 1000000007;
int n, m, l[MAX_N], dir[MAX_N], p[22][MAX_N];
pair<int, int> e[MAX_N];
vector<int> tr[MAX_N], g[MAX_N];
struct DSU {
int lab[MAX_N];
void init() {
memset(lab, 0, sizeof(lab));
}
int findset(int u) {
return lab[u]==0 ? u : lab[u]=findset(lab[u]);
}
void uni(int s, int t) {
s = findset(s); t = findset(t);
if (s==t)
return;
if (l[s]>l[t])
swap(s, t);
lab[t] = s;
}
} D1, D2, D3;
void enter() {
cin >> n >> m;
for (int i=1; i<n; ++i) {
int u, v; cin >> u >> v;
tr[u].push_back(v);
tr[v].push_back(u);
}
for (int i=1; i<=m; ++i) {
cin >> e[i].first >> e[i].second;
}
}
void fixRoot(int u) {
for (int i=0; i<tr[u].size(); ++i) {
int v = tr[u][i];
if (v!=p[0][u]) {
p[0][v] = u;
l[v] = l[u] + 1;
fixRoot(v);
}
}
}
int lca(int x, int y) {
for (int k=19; k>=0; --k)
if (l[p[k][x]]>=l[y])
x = p[k][x];
for (int k=19; k>=0; --k)
if (l[p[k][y]]>=l[x])
y = p[k][y];
for (int k=19; k>=0; --k) {
if (p[k][x]!=p[k][y]) {
x = p[k][x]; y = p[k][y];
}
}
while (x!=y) {
x = p[0][x]; y = p[0][y];
}
return x;
}
int prevNode(int anc, int u) {
if (u==anc)
return 0;
for (int k=19; k>=0; --k)
if (l[p[k][u]]>l[anc])
u = p[k][u];
return u;
}
void make_graph() {
D1.init();
D2.init();
for (int i=1; i<=m; ++i) {
int u = e[i].first, v = e[i].second, r = lca(u, v);
int prevU = prevNode(r, u), prevV = prevNode(r, v);
while (l[p[0][v]]>l[r]) {
int par = p[0][v];
g[par].push_back(v);
g[v].push_back(par);
D1.uni(v, par);
v = D1.findset(v);
}
while (l[p[0][u]]>l[r]) {
int par = p[0][u];
g[par].push_back(u);
g[u].push_back(par);
D2.uni(u, par);
u = D2.findset(u);
}
if (prevU && prevV) {
g[prevU].push_back(prevV);
g[prevV].push_back(prevU);
}
}
}
void visit(int u) {
int _next;
for (int i=0; i<g[u].size(); ++i) {
int v = g[u][i];
if (dir[v]==0) {
if (v==p[0][u] || u==p[0][v])
dir[v] = dir[u];
else
dir[v] = -dir[u];
visit(v);
}
}
}
bool check() {
D1.init();
D2.init();
//debug(dir[3]);
//debug(dir[4]);
for (int i=1; i<=m; ++i) {
int u = e[i].first, v = e[i].second, r = lca(u, v);
int prevU = prevNode(r, u), prevV = prevNode(r, v);
if (dir[prevU]==dir[prevV])
return false;
while (l[p[0][v]]>l[r]) {
int par = p[0][v];
if (dir[v]!=dir[par])
return false;
D1.uni(v, par);
v = D1.findset(v);
}
while (l[p[0][u]]>l[r]) {
int par = p[0][u];
if (dir[u]!=dir[par])
return false;
D2.uni(u, par);
u = D2.findset(u);
}
}
return true;
}
int main() {
//freopen(FILE_NAME".inp", "r", stdin);
//freopen(FILE_NAME".out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0);
enter();
l[1] = 1;
fixRoot(1);
for (int i=1; i<=19; ++i)
for (int j=1; j<=n; ++j)
p[i][j] = p[i-1][p[i-1][j]];
make_graph();
int res = 1;
for (int i=2; i<=n; ++i) {
if (dir[i]==0) {
dir[i] = 1;
visit(i);
res = (res * 2) % MOD;
}
}
//debug(res);
if (check()) {
cout << res;
}
else {
cout << 0;
}
}
Compilation message
usmjeri.cpp: In function 'void fixRoot(int)':
usmjeri.cpp:53:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<tr[u].size(); ++i) {
~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void visit(int)':
usmjeri.cpp:119:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<g[u].size(); ++i) {
~^~~~~~~~~~~~
usmjeri.cpp:118:6: warning: unused variable '_next' [-Wunused-variable]
int _next;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
416 ms |
42084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
644 ms |
83704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
83704 KB |
Output is correct |
| 2 |
Correct |
18 ms |
83704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
83704 KB |
Output is correct |
| 2 |
Correct |
17 ms |
83704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
83704 KB |
Output is correct |
| 2 |
Correct |
19 ms |
83704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
83704 KB |
Output is correct |
| 2 |
Correct |
22 ms |
83704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1328 ms |
83704 KB |
Output is correct |
| 2 |
Correct |
1359 ms |
88904 KB |
Output is correct |
| 3 |
Correct |
584 ms |
88904 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
102644 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
111216 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2082 ms |
118636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
