#define NDEBUG
#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();
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<int> badEdges[MAXN];
int comp[MAXN];
int num = 0;
inline void addEdge(int a, int b, v<int> adj[]) {
adj[a].push_back(b);
adj[b].push_back(a);
}
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) {
addEdge(a, b, badEdges);
}
}
createEdges(0, -1);
}
void printEdgeTree() {
FOR(i, 0, N) {
pf("lowDep[%d] := %d\n", i, lowDep[i]);
}
}
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 check(int x, int p, int col) {
comp[x] = col;
for (int c : adjEdges[x]) {
if (comp[c] == 0 && check(c, x, col) == -1)
return -1;
else if (comp[c] != comp[x])
return -1;
}
for (int c : badEdges[x]) {
if (comp[c] == 0 && check(c, x, -col) == -1)
return -1;
else if (comp[c] == comp[x])
return -1;
}
return 1;
}
int main() {
io();
inputTree();
// printTree();
makeEdgeTree();
// printEdgeTree();
ll ans = 1;
FOR(i, 1, N) if (comp[i] == 0) {
int res = check(i, -1, ++num);
if (res == -1) {
cout << "0\n";
return 0;
}
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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
43388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
300 ms |
87180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
26 ms |
87180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
27 ms |
87180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
28 ms |
87180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
28 ms |
87180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
459 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
564 ms |
87180 KB |
Output is correct |
| 3 |
Execution timed out |
2011 ms |
87180 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
531 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
495 ms |
87180 KB |
Output is correct |
| 3 |
Execution timed out |
2053 ms |
87180 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
507 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
462 ms |
87180 KB |
Output is correct |
| 3 |
Correct |
350 ms |
87180 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
543 ms |
87180 KB |
Output is correct |
| 2 |
Correct |
500 ms |
87180 KB |
Output is correct |
| 3 |
Execution timed out |
2071 ms |
87180 KB |
Time limit exceeded |
