#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
typedef long long ll;
typedef pair<int, int > pii;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();
int __builtin_clz(int x) { // #0s at beginning
RFORE(i, 31, 0)
if (((1 << i)&x) != 0) {
return 31 - i;
}
return 32;
}
const int MAXN = 300010;
int N, M;
v<int> adjTree[MAXN]; // rooted tree at 0. SZ nodes
int depth[MAXN];
int lowDep[MAXN];
template <int SZ> struct LCA {
int level[SZ]; // level of node i. node 0 is level 0
int anc[32][SZ]; // to walk 1<<k up from i. -1 if overflow.
int maxlvl = 0, maxlg = 0; // only need to consider jumping 2^{0...maxlg} aka maxlvl jmps
void init(int _n) {
dfs(0, -1, 0);
maxlg = 31 - __builtin_clz(maxlvl); // position of last '1'
FORE(i, 1, maxlg) FOR(j, 0, _n) {
anc[i][j] = -1;
if (anc[i - 1][j] != -1)
anc[i][j] = anc[i - 1][anc[i - 1][j]];
}
}
/* fills level, anc[0], maxlvl */
void dfs(int cur, int par, int lvl) {
anc[0][cur] = par, level[cur] = lvl, maxlvl = max(maxlvl, lvl);
for (auto chi : adjTree[cur]) if (chi != par) dfs(chi, cur, lvl + 1);
}
int walk(int a, int k) { // walk "a" k steps
int e = 31 - __builtin_clz(k); // position of last '1'
RFORE(i, e, 0) if (((1 << i)&k) != 0) a = anc[i][a];
return a;
}
int lca(int a, int b) {
if (level[a] < level[b]) swap(a, b);
a = walk(a, level[a] - level[b]);
if (a == b) return a;
RFORE(i, maxlg, 0) if (anc[i][a] != anc[i][b]) a = anc[i][a], b = anc[i][b];
a = anc[0][a], b = anc[0][b];
assert(a == b);
return a;
}
};
LCA<MAXN> lca;
v<int> adjEdges[MAXN];
v<pii> badEdges;
int comp[MAXN];
int num = 0;
void addEdge(int a, int b, v<int> adj[]) {
adj[a].push_back(b);
adj[b].push_back(a);
}
void colorEdges(int x, int p, int col) {
comp[x] = col;
for (int c : adjEdges[x]) if (comp[c] == 0)
colorEdges(c, x, col);
}
void createEdges(int x, int p) {
for (int c : adjTree[x]) if (c != p) {
createEdges(c, x);
lowDep[x] = min(lowDep[x], lowDep[c]);
if (lowDep[c] < depth[x])
addEdge(c, x, adjEdges);
}
}
void makeEdgeTree() {
FOR(i, 0, M) {
int a, b;
cin >> a >> b;
a--, b--;
int c = lca.lca(a, b);
lowDep[a] = min(lowDep[a], depth[c]);
lowDep[b] = min(lowDep[b], depth[c]);
if (a != c && b != c) {
badEdges.push_back({ a,b });
}
}
createEdges(0, -1);
FOR(i, 1, N) if (comp[i] == 0)
colorEdges(i, -1, ++num);
}
void printEdgeTree() {
FOR(i, 0, N) {
pf("lowDep[%d] := %d\n", i, lowDep[i]);
}
for (pii b : badEdges)
cout << b.first << " must be diff from " << b.second << "\n";
}
void dfsDepths(int x, int p, int d) {
depth[x] = d;
lowDep[x] = depth[x];
for (int c : adjTree[x]) if (c != p)
dfsDepths(c, x, d + 1);
}
void inputTree() {
cin >> N >> M;
FOR(i, 0, N - 1) {
int a, b;
cin >> a >> b;
a--, b--;
addEdge(a, b, adjTree);
}
dfsDepths(0, -1, 0);
lca.init(N);
}
void printTree() {
cout << N << "\n";
FOR(i, 0, N) {
pf("depth[%d] := %d\n", i, depth[i]);
for (int j : adjTree[i])
cout << i << " -> " << j << "\n";
}
}
int main() {
io();
inputTree();
//printTree();
makeEdgeTree();
//printEdgeTree();
for (pii opp : badEdges)
if (comp[opp.first] == comp[opp.second]) {
cout << 0 << "\n";
return 0;
}
ll ans = 1;
FOR(i, 0, num) {
ans <<= 1;
ans %= 1000000007LL;
}
cout << ans << "\n";
return 0;
}
void io() {
#ifdef LOCAL_PROJECT
freopen("input.in", "r", stdin);
freopen("output.out","w",stdout);
#else
// add i/o method of specific testing system
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
Compilation message
usmjeri.cpp: In function 'int __builtin_clz(int)':
usmjeri.cpp:23:5: warning: new declaration 'int __builtin_clz(int)' ambiguates built-in declaration 'int __builtin_clz(unsigned int)' [-Wbuiltin-declaration-mismatch]
int __builtin_clz(int x) { // #0s at beginning
^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
36472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
286 ms |
81124 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
472 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
533 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
523 ms |
81124 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
