#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define O_set tree<int, null_type, greater<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
const int MAXN = 300000 + 20, MAXM = 5000 + 20, MOD = 1000 * 1000 * 1000 + 7;
const long long INF = 1e9 + 10;
int par[MAXN][30], d[MAXN], x[MAXN], ans[MAXN], par2[MAXN], valpar[MAXN];
vector <pair <int, int> > vec[MAXN];
map <pair <int, int>, int> m;
map <int, int> vis;
vector <pair <int, int> > ds;
bool zer = 0;
void dfs(int u, int par1) {
par[u][0] = par1;
for (int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].first;
if (v != par1) {
d[v] = d[u] + 1;
dfs(v, u);
}
}
}
pair <int, int> parent(int u) {
vector <pair <int, int> > path;
path.push_back(make_pair(u, 0));
int x1 = 0;
while (par2[u] != u) {
x1 += valpar[u];
u = par2[u];
path.push_back(make_pair(u, x1));
}
for (int i = 0; i < path.size(); i++) {
int v = path[i].first;
int val = path[i].second;
par2[v] = u;
valpar[v] = (x1 - val) % 2;
}
return make_pair(u, x1 % 2);
}
void dsu(int u, int v, int x) {
pair <int, int> d = parent(u);
int par1 = d.first;
int val1 = d.second;
d = parent(v);
int par11 = d.first;
int val11 = d.second;
if (par1 == par11) {
if ((val1 + val11 + x) % 2 == 1)
zer = 1;
}
else {
par2[par1] = par11;
if ((val1 + val11) % 2 == x)
valpar[par1] = 0;
else
valpar[par1] = 1;
}
}
void dfs1(int u, int par1) {
for (int i = 0; i < vec[u].size(); i++) {
int v = vec[u][i].first;
int ind = vec[u][i].second;
if (v != par1) {
dfs1(v, u);
if (x[v] > 0) {
dsu(m[make_pair(u, par1)], m[make_pair(v, u)], 0);
}
x[u] += x[v];
}
}
}
int lca(int a, int b) {
if (d[a] < d[b])
swap(a, b);
int dis = d[a] - d[b] - 1;
int ghabl = a;
for (int i = 0; i < 22; i++) {
if ((1 << i) & dis) {
ghabl = a;
a = par[a][i];
}
}
if (par[a][0] == b) {
x[a]--;
x[b]--;
return b;
}
a = par[a][0];
for (int i = 21; i >= 0; i--) {
if (par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
}
int par1 = par[a][0];
int yal = m[make_pair(a, par1)];
int yal1 = m[make_pair(b, par1)];
// dsu(yal, yal1, 1);
ds.push_back(make_pair(yal1, yal));
x[a]--;
x[b]--;
return par[a][0];
}
void solve() {
int n, q;
cin >> n >> q;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
vec[u].push_back(make_pair(v, i));
vec[v].push_back(make_pair(u, i));
m[make_pair(u, v)] = i;
m[make_pair(v, u)] = i;
}
for (int i = 1; i <= n - 1; i++)
par2[i] = i;
dfs(1, 0);
for (int j = 1; j < 22; j++) {
for (int i = 1; i <= n; i++) {
if (par[i][j - 1] != -1)
par[i][j] = par[par[i][j - 1]][j - 1];
else
par[i][j] = -1;
}
}
while (q--) {
int a, b;
cin >> a >> b;
int par1 = lca(a, b);
x[a]++;
x[b]++;
}
// for (int i = 1; i <= n; i++)
// cout << x[i] << " ";
// cout << endl;
dfs1(1, 0);
for (int i = 0; i < ds.size(); i++) {
dsu(ds[i].first, ds[i].second, 1);
}
int ans = 0;
for (int i = 1; i <= n - 1; i++) {
pair <int, int> d = parent(i);
int u = d.first;
// cout << u << " ";
if (!vis[u]) {
vis[u] = 1;
ans++;
}
}
long long x1 = 1;
for (int i = 0; i < ans; i++)
x1 = x1 * 2 % MOD;
if (zer) {
cout << 0 << endl;
}
else
cout << x1 << endl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int q = 1;
// cin >> q;
while (q--) {
solve();
}
}
Compilation message
usmjeri.cpp: In function 'void dfs(int, int)':
usmjeri.cpp:19:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 0; i < vec[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
usmjeri.cpp: In function 'std::pair<int, int> parent(int)':
usmjeri.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for (int i = 0; i < path.size(); i++) {
| ~~^~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs1(int, int)':
usmjeri.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for (int i = 0; i < vec[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
usmjeri.cpp:75:7: warning: unused variable 'ind' [-Wunused-variable]
75 | int ind = vec[u][i].second;
| ^~~
usmjeri.cpp: In function 'int lca(int, int)':
usmjeri.cpp:93:6: warning: variable 'ghabl' set but not used [-Wunused-but-set-variable]
93 | int ghabl = a;
| ^~~~~
usmjeri.cpp: In function 'void solve()':
usmjeri.cpp:157:7: warning: unused variable 'par1' [-Wunused-variable]
157 | int par1 = lca(a, b);
| ^~~~
usmjeri.cpp:168:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | for (int i = 0; i < ds.size(); i++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
259 ms |
53740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
623 ms |
149100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
7788 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7788 KB |
Output is correct |
| 2 |
Correct |
8 ms |
8044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
8940 KB |
Output is correct |
| 2 |
Correct |
17 ms |
9068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1108 ms |
109792 KB |
Output is correct |
| 2 |
Correct |
1171 ms |
107792 KB |
Output is correct |
| 3 |
Correct |
805 ms |
75016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1414 ms |
111364 KB |
Output is correct |
| 2 |
Correct |
1326 ms |
111916 KB |
Output is correct |
| 3 |
Correct |
839 ms |
75652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1321 ms |
112212 KB |
Output is correct |
| 2 |
Correct |
1160 ms |
108260 KB |
Output is correct |
| 3 |
Correct |
948 ms |
75976 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1389 ms |
112428 KB |
Output is correct |
| 2 |
Correct |
1225 ms |
112672 KB |
Output is correct |
| 3 |
Correct |
992 ms |
70252 KB |
Output is correct |
