This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int logN = 20;
struct tree{
int n, timer;
vector<vector<int>> adj;
vector<vector<int>> par;
vector<int> depth, st, en;
void add_edge(int a, int b){
adj[a].push_back(b);
adj[b].push_back(a);
}
tree(int n) : n(n), adj(n), par(logN, vector<int>(n)), depth(n), st(n), en(n), timer(0){}
void input(){
for(int i = 1; i < n; i++){
int x, y;
scanf("%d %d", &x, &y);
x--; y--;
add_edge(x, y);
}
}
void rootify(int r){
function<void(int, int, int)> dfs = [&](int s, int d, int p){
st[s] = ++timer;
depth[s] = d;
par[0][s] = p;
for(int v : adj[s])
if(v != p)
dfs(v, d + 1, s);
en[s] = timer;
};
dfs(r, 1, r);
for(int j = 1;j<logN;j++)
for(int i = 0; i < n;i++)
par[j][i] = par[j-1][par[j-1][i]];
}
int lca(int a, int b){
if(depth[a] < depth[b]) swap(a,b);
int l = depth[a] - depth[b];
for(int i = 0; i < logN; i++) if(l >> i & 1)
a = par[i][a];
if(a == b) return a;
for(int i = logN - 1; i >= 0; i--)
if(par[i][a] != par[i][b])
a = par[i][a], b = par[i][b];
return par[0][a];
}
int getKth(int x, int k){
for(int i = 0; i < logN; i++) if(k >> i & 1) x = par[i][x];
return x;
}
};
struct dsu{
int n, comps, ok;
vector<int> par;
dsu(int n) : n(n), par(n), comps(n - 1), ok(1){
for(int i = 0; i < n; i++) par[i] = 2 * i;
}
int root(int x){
int h = par[x];
int p = h >> 1;
if(p == x) return h;
return par[x] = root(p) ^ (h & 1);
}
bool merge(int x, int y, int e){
int X = root(x), Y = root(y);
x = X >> 1; y = Y >> 1;
int parity_x = X & 1, parity_y = Y & 1;
if(x == y){
if(parity_x ^ parity_y ^ e) ok = 0;
return 0;
}
par[x] = 2 * y + (parity_x ^ parity_y ^ e);
comps--;
return 1;
}
};
int main(){
int n, m;
scanf("%d %d", &n, &m);
tree T(n);
T.input();
T.rootify(0);
dsu D(n);
dsu D2(n);
function<void(int, int)> attach = [&](int u, int l){
while(T.depth[u] >= T.depth[l] + 2){
D.merge(u, T.par[0][u], 0);
D2.merge(u, T.par[0][u], 0);
u = D.root(u) >> 1;
}
};
for(int i = 0; i < m; i++){
int u, v;
scanf("%d %d", &u, &v);
u--; v--;
if(T.depth[u] < T.depth[v]) swap(u, v);
int l = T.lca(u, v);
attach(u, l);
attach(v, l);
if(v != l){
D2.merge(u, v, 1);
}
}
int ans = D2.ok;
for(int i = 0; i < D2.comps; i++) ans = (ans * 2) % 1000000007;
printf("%d\n", ans);
}
Compilation message (stderr)
usmjeri.cpp: In constructor 'tree::tree(int)':
usmjeri.cpp:10:28: warning: 'tree::en' will be initialized after [-Wreorder]
vector<int> depth, st, en;
^~
usmjeri.cpp:7:12: warning: 'int tree::timer' [-Wreorder]
int n, timer;
^~~~~
usmjeri.cpp:15:5: warning: when initialized here [-Wreorder]
tree(int n) : n(n), adj(n), par(logN, vector<int>(n)), depth(n), st(n), en(n), timer(0){}
^~~~
usmjeri.cpp: In constructor 'dsu::dsu(int)':
usmjeri.cpp:60:17: warning: 'dsu::par' will be initialized after [-Wreorder]
vector<int> par;
^~~
usmjeri.cpp:59:12: warning: 'int dsu::comps' [-Wreorder]
int n, comps, ok;
^~~~~
usmjeri.cpp:61:5: warning: when initialized here [-Wreorder]
dsu(int n) : n(n), par(n), comps(n - 1), ok(1){
^~~
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &m);
~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:102:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp: In member function 'void tree::input()':
usmjeri.cpp:19:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~~
# | 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... |