#include <bits/stdc++.h>
using namespace std;
#define int long long
//only case left: find when it is 0
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 3e5 + 5, M = 3e5 + 5, MOD = 1e9 + 7;
int depth[N];
vector<array<int, 3> > special_pairs(M);
vector<int> g[N];
int dp[19][N];
int tin[N], tout[N], tim = 0;
int parent[N];
int power(int a, int b)
{
if(b == 0) return 1;
if(b == 1) return a;
int x = power(a, b / 2);
x = (x * x) % MOD;
if(b & 1)
{
x = (x * a) % MOD;
}
return x;
}
void dfs(int node, int par)
{
tin[node] = ++tim;
dp[0][node] = par;
for(int to: g[node])
{
if(to == par) continue;
depth[to] = depth[node] + 1;
dfs(to, node);
}
tout[node] = ++tim;
}
int Find(int x)
{
if(x == parent[x]) return x;
return parent[x] = Find(parent[x]);
}
void Unite(int x, int y)
{
x = Find(x), y = Find(y);
parent[x] = y;
}
int LCA(int x, int y)
{
if(depth[x] > depth[y]) swap(x, y);
int diff = depth[y] - depth[x];
for(int i = 18; i >= 0; i--)
{
if(diff & (1 << i))
{
y = dp[i][y];
}
}
if(x == y) return x;
for(int i = 18; i >= 0; i--)
{
if(dp[i][x] != dp[i][y])
{
x = dp[i][x];
y = dp[i][y];
}
}
return dp[0][x];
}
void Solve()
{
int n, m;
cin >> n >> m;
for(int i = 1; i < n; i++)
{
parent[i] = i;
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
parent[n] = n;
depth[1] = 0;
dfs(1, -1);
for(int i = 1; i < 19; i++)
{
for(int j = 1; j <= n; j++)
{
if(dp[i - 1][j] == -1)
{
dp[i][j] = -1;
}
else
{
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
}
}
for(int i = 1; i <= m; i++)
{
int u, v;
cin >> u >> v;
int lca = LCA(u, v);
special_pairs[i] = {u, lca, v};
}
for(int i = 1; i <= m; i++)
{
// cout << special_pairs[i][0] << " " << special_pairs[i][1] << " " << special_pairs[i][2] << "\n";
int cur = special_pairs[i][0];
cur = Find(cur);
while(depth[cur] > depth[special_pairs[i][1]])
{
Unite(cur, dp[0][cur]);
cur = Find(cur);
}
cur = special_pairs[i][2];
cur = Find(cur);
while(depth[cur] > depth[special_pairs[i][1]])
{
Unite(cur, dp[0][cur]);
cur = Find(cur);
}
}
int components = 0;
for(int i = 1; i <= n; i++)
{
if(Find(i) == i)
{
components++;
}
}
cout << power(2LL, components) << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
104 ms |
43596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
197 ms |
99036 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
9 ms |
14836 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
14836 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
15 ms |
15732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
12 ms |
15784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
256 ms |
87196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
559 ms |
87344 KB |
Output is correct |
2 |
Correct |
541 ms |
87336 KB |
Output is correct |
3 |
Incorrect |
321 ms |
63028 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
528 ms |
87420 KB |
Output is correct |
2 |
Incorrect |
267 ms |
87320 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
474 ms |
87716 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |