이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MOD = 1E9 + 7;
const int MAXN = 3E5 + 5;
const int LOG = 25;
int p[LOG][MAXN];
int depth[MAXN];
int get(int a, int b) {
for(int i = LOG -1; i >= 0; i--) {
if(b & (1 << i)) {
a = p[i][a];
}
}
return a;
}
int par[MAXN];
struct DSU {
int n;
DSU(int n) : n(n) {
// 23 orz
iota(par, par + n, 0);
}
int get(int x) {
if(par[x] == x) {
return x;
}
return par[x] = get(par[x]);
}
bool same(int a, int b) {
return get(a) == get(b);
}
bool unite(int u, int v) {
if(same(u, v)) {
return false;
}
u = get(u);
v = get(v);
par[u] = v;
return true;
}
};
int lca(int a, int b) {
if(depth[a] > depth[b]) {
swap(a, b);
}
b = get(b, depth[b] - depth[a]);
if(a == b) {
return a;
}
for(int lg = LOG -1; lg >= 0; lg--) {
if(p[lg][a] != p[lg][b]) {
a = p[lg][a];
b = p[lg][b];
}
}
return p[0][a];
}
#define ONLINE_JUDGE
void solve() {
int n, m;
cin >> n >> m;
vector <int> adj[n +1];
for(int i = 1; i <= n -1; i++) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
function <void(int, int)> dfs = [&](int node, int par) -> void {
p[0][node] = par;
depth[node] = depth[par] +1;
for(int &child : adj[node]) {
if(child != par) {
dfs(child, node);
}
}
};
dfs(1, 0);
for(int lg = 1; lg < LOG; lg++) {
for(int i = 1; i <= n; i++) {
p[lg][i] = p[lg -1][p[lg -1][i]];
}
}
map <pair <int, int>, int> mp;
DSU dsu(n +1);
function <void(int, int, int)> dfsP = [&](int a, int b, int ty) -> void {
while(a != b) {
dsu.unite(a, p[0][a]);
mp[{a, p[0][a]}] |= ty;
a = p[0][a];
}
};
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
if(depth[a] < depth[b]) {
swap(a, b);
} else if(depth[a] == depth[b]) {
if(a < b) {
swap(a, b);
}
}
int c = lca(a, b);
dfsP(a, c, 1);
dfsP(b, c, 2);
}
for(auto &[x, y] : mp) {
if(y == 3) {
cout << 0;
return;
}
}
int ans = 1;
for(int i = 1; i <= n; i++) {
if(dsu.get(i) == i) {
ans = (ans * 2) % MOD;
}
}
cout << ans;
return;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int t = 1; //cin >> t;
for(int i = 1; i <= t; i++) {
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |