#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;
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() - 1; i++) {
int v = path[i].first;
int val = path[i].second;
par2[v] = u;
valpar[v] = (x1 - val) % 2;
}
return make_pair(u, x1);
}
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 a;
}
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);
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);
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:18: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]
18 | for (int i = 0; i < vec[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
usmjeri.cpp: In function 'std::pair<int, int> parent(int)':
usmjeri.cpp:37: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]
37 | for (int i = 0; i < path.size() - 1; i++) {
| ~~^~~~~~~~~~~~~~~~~
usmjeri.cpp: In function 'void dfs1(int, int)':
usmjeri.cpp:72: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]
72 | for (int i = 0; i < vec[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
usmjeri.cpp:74:7: warning: unused variable 'ind' [-Wunused-variable]
74 | int ind = vec[u][i].second;
| ^~~
usmjeri.cpp: In function 'int lca(int, int)':
usmjeri.cpp:92:6: warning: variable 'ghabl' set but not used [-Wunused-but-set-variable]
92 | int ghabl = a;
| ^~~~~
usmjeri.cpp: In function 'void solve()':
usmjeri.cpp:155:7: warning: unused variable 'par1' [-Wunused-variable]
155 | int par1 = lca(a, b);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
53860 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
621 ms |
148520 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
8064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 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 |
9068 KB |
Output is correct |
| 2 |
Correct |
13 ms |
9196 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
9068 KB |
Output is correct |
| 2 |
Correct |
14 ms |
9216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1114 ms |
108916 KB |
Output is correct |
| 2 |
Correct |
1224 ms |
107004 KB |
Output is correct |
| 3 |
Correct |
782 ms |
74348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1368 ms |
108640 KB |
Output is correct |
| 2 |
Correct |
1332 ms |
109036 KB |
Output is correct |
| 3 |
Correct |
864 ms |
74248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1380 ms |
109676 KB |
Output is correct |
| 2 |
Correct |
1159 ms |
108012 KB |
Output is correct |
| 3 |
Correct |
868 ms |
74444 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1311 ms |
110236 KB |
Output is correct |
| 2 |
Correct |
1279 ms |
110700 KB |
Output is correct |
| 3 |
Correct |
985 ms |
70508 KB |
Output is correct |
