제출 #51561

#제출 시각아이디문제언어결과실행 시간메모리
51561Adhyyan1252Usmjeri (COCI17_usmjeri)C++11
0 / 140
1219 ms103892 KiB
#include<bits/stdc++.h> using namespace std; #define NMAX 300005 #define LOGN 19 vector<int> g[NMAX]; int f[NMAX][LOGN]; int dep[NMAX]; void root(int cur, int par = -1, int depth = 0){ f[cur][0] = par; dep[cur] = depth; for(auto child: g[cur]){ if(child == par) continue; root(child, cur, depth+1); } } int n, m; void init(){ for(int i = 1; i < LOGN; i++) for(int j = 0; j < n; j++) if(f[j][i-1] != -1) f[j][i] = f[f[j][i-1]][i-1]; else f[j][i] = -1; } int lca(int a, int b){ if(dep[a] > dep[b]) swap(a, b); // a has lesser depth for(int i = 0; i < LOGN; i++){ if(dep[b] - (1<<i) >= dep[a]){ b = f[b][i]; } } if(a == b) return a; for(int i = 0; i < LOGN; i++){ if(f[a][i] != f[b][i]){ a = f[a][i]; b = f[b][i]; } } return f[a][0]; } struct node{ int a, b, par; }; node ps[NMAX]; vector<pair<int, bool> > h[NMAX]; int low[NMAX]; int connect(int cur, int par){ for(auto child: g[cur]){ if(child == par) continue; low[cur] = min(low[cur], connect(child, cur)); } if(cur != 0) if(low[cur] < dep[cur] - 1){ h[cur].push_back({f[cur][0], false}); h[f[cur][0]].push_back({cur, false}); } return low[cur]; } bool pos = true; int col[NMAX]; void check(int cur, int ccol){ if(col[cur] != -1){ if(col[cur] != ccol){ pos = false; } return; } col[cur] = ccol; for(auto child: h[cur]){ check(child.first, ccol^child.second); } } int main(){ cin>>n>>m; for(int i = 0; i < n-1; i++){ int u, v; cin>>u>>v; u--; v--; g[u].push_back(v); g[v].push_back(u); } for(int i = 0; i < m; i++){ cin>>ps[i].a>>ps[i].b; ps[i].a--; ps[i].b--; } root(0); init(); for(int i = 0; i < n; i++){ low[i] = 10000000; col[i] = -1; } for(int i = 0; i < m; i++){ ps[i].par = lca(ps[i].a, ps[i].b); if(ps[i].par == ps[i].a || ps[i].par == ps[i].b){ }else{ h[ps[i].a].push_back({ps[i].b, true}); h[ps[i].b].push_back({ps[i].a, true}); } low[ps[i].a] = min(low[ps[i].a], dep[ps[i].par]); low[ps[i].b] = min(low[ps[i].b], dep[ps[i].par]); //cout<<"LCA: "<<ps[i].par<<endl; } connect(0, -1); // for(int i = 1; i < n; i++){ // //cout<<i<<" : "; // for(auto child: h[i]){ // //cout<<"( "<<child.first<<", "<<child.second<<" ) "; // } // cout<<endl; // } int comp = 0; for(int i = 1; i < n; i++){ if(col[i] == -1){ comp++; check(i, 0); } } if(pos){ long long ans = 1; for(int i = 0; i < comp; i++) ans = (ans*2)%1000000007; cout<<ans<<endl; }else{ cout<<0<<endl; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...