/*
I find it wholesome to be alone the greater part of the time.
To be in company, even with the best, is soon wearisome and dissipating.
I love to be alone.
I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 4e5 + 1;
const int Mod = 1e9 + 7;
//const int inf =
int n, m;
int lift[maxN][20];
int depth[maxN];
int dp[maxN];
struct TDSU{
vector <int> lab;
TDSU(){}
TDSU(int _n){
lab.resize(_n, -1);
}
inline void resize(int _n){
lab.resize(_n, -1);
}
inline int find_set(int u){
if (lab[u] < 0) return u;
return lab[u] = find_set(lab[u]);
}
inline void unite(int u, int v){
u = find_set(u);
v = find_set(v);
if (u == v) return;
if (lab[u] > lab[v]) swap(u, v);
lab[u] += lab[v];
lab[v] = u;
}
};
TDSU dsu;
vector <int> adj[maxN];
void pre_dfs(int u, int p){
lift[u][0] = p;
for (int i = 1; i < 20; ++i){
lift[u][i] = lift[lift[u][i - 1]][i - 1];
}
depth[u] = depth[p] + 1;
for (int i: adj[u]){
if (i == p) continue;
pre_dfs(i, u);
}
}
inline int lca(int u, int v){
if (depth[u] < depth[v]) swap(u, v);
int k = depth[u] - depth[v];
while (k){
int t = __builtin_ctz(k);
u = lift[u][t];
k -= 1 << t;
}
if (u == v) return u;
for (int i = 19; i >= 0; --i){
if (lift[u][i] != lift[v][i]){
u = lift[u][i];
v = lift[v][i];
}
}
return lift[u][0];
}
void dfs(int u, int p){
for (int i: adj[u]){
if (i == p) continue;
dfs(i, u);
dp[u] += dp[i];
}
for (int i: adj[u]){
if (i == p) continue;
if (dp[i]){
dsu.unite(i, u);
dsu.unite(i + n, u + n);
}
}
}
inline int jump(int u, int k){
while (k > 0){
int t = __builtin_ctz(k);
u = lift[u][t];
k -= 1 << t;
}
return u;
}
void Init(){
cin >> n >> m;
dsu.resize(2 * n + 1);
for (int i = 1; i < n; ++i){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
pre_dfs(1, 0);
for (int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
int p = lca(u, v);
++dp[u];
++dp[v];
int x = jump(u, depth[u] - depth[p] - 1);
int y = jump(v, depth[v] - depth[p] - 1);
--dp[x];
--dp[y];
//cerr << u << " " << v << " " << x << " " << y << "\n";
if (p == u || p == v) continue;
dsu.unite(u + n, v);
dsu.unite(u, v + n);
}
//for (int i = 1; i <= 8; ++i) cerr << dsu.find_set(i) << " ";
dfs(1, 0);
for (int i = 1; i <= n; ++i){
if (dsu.find_set(i) == dsu.find_set(i + n)){
cout << 0;
exit(0);
}
}
map <int, bool> mp;
ll ans = 1;
for (int i = 2; i <= n; ++i){
if (!mp[dsu.find_set(i)]){
ans <<= 1;
if (ans > Mod) ans -= Mod;
}
mp[dsu.find_set(i)] = mp[dsu.find_set(i + n)] = 1;
}
cout << ans;
}
#define debug
#define taskname "test"
signed main(){
faster
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
#ifndef debug
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
#endif // debug
}
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | freopen(taskname".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
usmjeri.cpp:154:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
154 | freopen(taskname".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
38548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
415 ms |
102072 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
9 ms |
9996 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9792 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9992 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
10504 KB |
Output is correct |
| 2 |
Correct |
8 ms |
10392 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
10580 KB |
Output is correct |
| 2 |
Correct |
10 ms |
10324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
474 ms |
79796 KB |
Output is correct |
| 2 |
Correct |
496 ms |
76528 KB |
Output is correct |
| 3 |
Correct |
203 ms |
38732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
555 ms |
79300 KB |
Output is correct |
| 2 |
Correct |
517 ms |
81176 KB |
Output is correct |
| 3 |
Correct |
250 ms |
40184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
528 ms |
80316 KB |
Output is correct |
| 2 |
Correct |
504 ms |
77724 KB |
Output is correct |
| 3 |
Correct |
245 ms |
40052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
758 ms |
80156 KB |
Output is correct |
| 2 |
Correct |
483 ms |
81944 KB |
Output is correct |
| 3 |
Correct |
235 ms |
38552 KB |
Output is correct |
