#include<bits/stdc++.h>
using namespace std;
const int const1 = 1e9 + 7;
long long power(int a, int b){
if(b == 0)
{
return 1;
}
else if(b % 2 == 0){
long long t= power(a, b / 2);
return t * t % const1;
}
else
{
long long t= power(a, b / 2);
t = t * t % const1;
return t * a % const1;
}
}
vector <int> used;
vector <vector <pair <int, int> > > g;
vector <vector <int> > pred;
vector <int> tin, tout, h, h1;
int timer = 0;
bool pr(int a, int b)
{
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
void dfs(int v, int p = -1)
{
tin[v] = timer++;
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v][i].first;
if(to != p)
{
pred[0][to] = v;
h[to] = h[v] + 1;
dfs(to, v);
}
}
tout[v] = timer++;
}
vector <vector <int> > g1;
vector <int> dsu, rang;
vector <pair <int, int> > vec;
int lca(int a, int b)
{
if(pr(a, b))
{
for(int j = pred.size() - 1; j >= 0; j--)
{
if(!pr(pred[j][b], a))
{
b = pred[j][b];
}
}
return pred[0][b];
}
else if(pr(b, a))
{
for(int j = pred.size() - 1; j >= 0; j--){
if(!pr(pred[j][a], b))
{
a = pred[j][a];
}
}
return pred[0][a];
}
else
{
for(int j = pred.size() - 1; j >= 0; j--)
{
if(!pr(pred[j][a], b))
{
a = pred[j][a];
}
}
for(int j = pred.size() - 1; j >= 0; j--)
{
if(!pr(pred[j][b], a))
{
b = pred[j][b];
}
}
int v = pred[0][a];
int ind1 = lower_bound(g[v].begin(), g[v].end(), make_pair(a, 0)) - g[v].begin();
int ind2 = lower_bound(g[v].begin(), g[v].end(), make_pair(b, 0)) - g[v].begin();
ind1 = g[v][ind1].second;
ind2 = g[v][ind2].second;
vec.push_back({ind1, ind2});
return pred[0][a];
}
}
int qwer(int a)
{
if(a == dsu[a])
{
return a;
}
else
{
return dsu[a] = qwer(dsu[a]);
}
}
void unite(int a, int b)
{
a = qwer(a);
b = qwer(b);
if(a != b)
{
if(rang[a] < rang[b])
{
swap(a, b);
}
dsu[b] = a;
if(rang[a] == rang[b])
{
rang[a]++;
}
}
}
void dfs1(int v, int p = -1, int pind = -1)
{
for(int i = 0; i < g[v].size(); i++){
int to = g[v][i].first;
if(to != p)
{
dfs1(to, v, g[v][i].second);
if(h1[to] < h[v])
{
unite(pind, g[v][i].second);
}
h1[v] = min(h1[v], h1[to]);
}
}
}
void dfs2(int v, int c)
{
used[v] = c;
for(int i = 0; i < g1[v].size(); i++)
{
int to = g1[v][i];
if(used[to] == -1)
{
dfs2(to, 1 - c);
}
else if(used[to] != 1 - c)
{
cout << 0;
exit(0);
}
}
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, m;
cin >> n >> m;
if(n == 1)
{
cout << 2;
return 0;
}
g1.resize(n - 1);
dsu.resize(n - 1);
rang.resize(n - 1);
g.resize(n);
h.resize(n);
h1.resize(n, 1e9);
int t = log2(n) + 1;
pred.resize(t, vector <int> (n));
tin.resize(n);
tout.resize(n);
for(int i = 0; i < n - 1; i++)
{
int a, b;
cin >> a >> b;
a--;
b--;
g[a].push_back({b, i});
g[b].push_back({a, i});
}
for(int i = 0; i < n; i++){
sort(g[i].begin(), g[i].end());
}
dfs(0);
for(int j = 1; j < t; j++)
{
for(int i = 0; i < n; i++)
{
pred[j][i] = pred[j - 1][pred[j - 1][i]];
}
}
for(int i = 0; i < n - 1; i++){
dsu[i] = i;
rang[i] = 1;
}
while(m--)
{
int a, b;
cin >> a >> b;
a--;
b--;
if(a == b)
{
continue;
}
int v = lca(a, b);
h1[a] = min(h1[a], h[v]);
h1[b] = min(h1[b], h[v]);
}
dfs1(0);
for(int i = 0; i < vec.size(); i++)
{
int a = vec[i].first;
int b = vec[i].second;
a = qwer(a);
b = qwer(b);
g1[a].push_back(b);
g1[b].push_back(a);
}
used.resize(n, -1);
int cnt = 0;
for(int i = 0; i < n - 1; i++)
{
int v = qwer(i);
if(used[v] == -1)
{
cnt++;
dfs2(v, 0);
}
}
cout << power(2, cnt);
return 0;
}
Compilation message
usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:32:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++)
~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs1(int, int, int)':
usmjeri.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g[v].size(); i++){
~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs2(int, int)':
usmjeri.cpp:141:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < g1[v].size(); i++)
~~^~~~~~~~~~~~~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:215:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec.size(); i++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
169 ms |
25328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
312 ms |
77796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
6 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
512 KB |
Output is correct |
| 2 |
Correct |
6 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1280 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1152 KB |
Output is correct |
| 2 |
Correct |
8 ms |
1152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
560 ms |
58212 KB |
Output is correct |
| 2 |
Correct |
625 ms |
66020 KB |
Output is correct |
| 3 |
Correct |
347 ms |
42472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
964 ms |
62208 KB |
Output is correct |
| 2 |
Correct |
779 ms |
70000 KB |
Output is correct |
| 3 |
Correct |
417 ms |
45668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
726 ms |
62560 KB |
Output is correct |
| 2 |
Correct |
663 ms |
65508 KB |
Output is correct |
| 3 |
Correct |
658 ms |
45668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
700 ms |
62432 KB |
Output is correct |
| 2 |
Correct |
657 ms |
70088 KB |
Output is correct |
| 3 |
Correct |
379 ms |
40424 KB |
Output is correct |
