#include <bits/stdc++.h>
using namespace std;
const int N = 300010, LOG = 20;
const int MOD = 1000000007;
inline int add(int u, int v) {u += v; if (u >= MOD) u -= MOD; return u;}
inline int sub(int u, int v) {u -= v; if (u < 0) u += MOD; return u;}
inline int mul(int u, int v) {return (long long)u * v % MOD;};
inline int power(int u, int v) {int res = 1; while (v) {if (v & 1) res = mul(res, u); u = mul(u, u); v >>= 1;} return res;}
inline int inv(int u) {return power(u, MOD - 2);}
int n, m;
vector<int> adj[N];
vector<pair<int, int> > adj2[N];
int lv[N], anc[LOG][N], cnt[N], used[N], dir[N];
int lca(int u, int v) {
if (lv[u] > lv[v]) {
swap(u, v);
}
int h = lv[v] - lv[u];
for (int i = LOG - 1; i >= 0; i--) {
if ((h >> i) & 1) {
v = anc[i][v];
}
}
if (u == v) {
return u;
}
for (int i = LOG - 1; i >= 0; i--) {
if (anc[i][u] != anc[i][v]) {
u = anc[i][u];
v = anc[i][v];
}
}
return anc[0][u];
}
void dfsInit(int u, int p) {
lv[u] = lv[p] + 1;
anc[0][u] = p;
for (int i = 1; i < LOG; i++) {
anc[i][u] = anc[i - 1][anc[i - 1][u]];
}
for (int v : adj[u]) {
if (v != p) {
dfsInit(v, u);
}
}
}
void dfsCalc(int u, int p) {
for (int v : adj[u]) {
if (v != p) {
dfsCalc(v, u);
cnt[u] += cnt[v];
}
}
if (cnt[u]) {
adj2[u].emplace_back(p, 0);
adj2[p].emplace_back(u, 0);
}
}
bool dfsRes(int u, int d) {
if (used[u]) {
return dir[u] == d;
}
used[u] = 1;
dir[u] = d;
for (pair<int, int> v : adj2[u]) {
if (!dfsRes(v.first, d ^ v.second)) {
return 0;
}
}
return 1;
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
dfsInit(1, 0);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
int w = lca(u, v);
cnt[u]++, cnt[v]++;
cnt[w] -= 2;
if (u != w && v != w) {
adj2[u].emplace_back(v, 1);
adj2[v].emplace_back(u, 1);
}
}
dfsCalc(1, 0);
// for (int i = 1; i <= n; i++) {
// cout << cnt[i] << endl;
// }
int res = 1;
for (int i = 1; i <= n; i++) {
if (!used[i]) {
res = mul(res, 2);
if (!dfsRes(i, 0)) {
res = 0;
}
}
}
cout << res << endl;
return 0;
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:82:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
^
usmjeri.cpp:85:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
^
usmjeri.cpp:92:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
146 ms |
37752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
313 ms |
82536 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
82536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
82536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
19 ms |
82536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
20 ms |
82536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
510 ms |
82536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
693 ms |
86020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
614 ms |
94104 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
625 ms |
102368 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
