#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
llo n,m;
llo mod=1e9+7;
vector<pair<llo,llo>> adj[300001];
vector<pair<llo,llo>> adj2[300001];
llo par[300001][20];
llo par2[300001];
llo st[300001];
llo endd[300001];
llo lev[300001];
llo co=0;
void dfs(llo no,llo par3=-1,llo levv=0,llo par4=-1){
par[no][0]=par3;
lev[no]=levv;
par2[no]=par4;
st[no]=co;
co+=1;
for(auto j:adj[no]){
if(j.a==par3){
continue;
}
dfs(j.a,no,levv+1,j.b);
}
endd[no]=co-1;
}
llo kk(llo no,llo dd){
for(llo j=0;j<20;j++){
if(((1<<j)&dd)){
no=par[no][j];
}
}
return no;
}
llo tree[310001];
void u(llo i,llo j){
while(i<310001){
tree[i]+=j;
i+=(i&-i);
}
}
llo ss(llo i){
llo su=0;
while(i>0){
su+=tree[i];
i-=(i&-i);
}
return su;
}
vector<llo> mm[300001];
pair<llo,pair<llo,llo>> lca(llo aa,llo bb){
llo stt=0;
if(lev[aa]>lev[bb]){
stt=1;
swap(aa,bb);
}
bb=kk(bb,lev[bb]-lev[aa]);
/* if(aa==bb){
while(true){
continue;
}
}*/
for(llo j=19;j>=0;j--){
if(par[aa][j]!=par[bb][j]){
aa=par[aa][j];
bb=par[bb][j];
}
}
/* if(aa==bb){
while(true){
continue;
}
}*/
if(stt==0){
return {par[aa][0],{aa,bb}};
}
else{
return {par[aa][0],{bb,aa}};
}
}
void dfs2(llo no,llo par3=-1){
for(auto j:adj[no]){
if(j.a!=par3){
dfs2(j.a,no);
}
}
for(auto j:mm[no]){
u(j+1,-1);
}
for(auto j:adj[no]){
if(j.a!=par3){
if((ss(endd[j.a]+1)-ss(st[j.a]))>0){
adj2[par2[no]].pb({j.b,0});
adj2[j.b].pb({par2[no],0});
}
}
}
}
llo vis[300001];
llo ok=1;
void dfs3(llo no,llo val=0){
vis[no]=val+1;
for(auto j:adj2[no]){
if(vis[j.a]==0){
dfs3(j.a,(vis[no]-1)^j.b);
}
else{
if((vis[j.a]-1)!=((vis[no]-1)^j.b)){
ok=0;
}
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(llo i=0;i<n-1;i++){
llo aa,bb;
cin>>aa>>bb;
aa--;
bb--;
adj[aa].pb({bb,i});
adj[bb].pb({aa,i});
}
dfs(0);
/* if(n>5000){
return 0;
}*/
for(llo j=1;j<20;j++){
for(llo i=0;i<n;i++){
if(par[i][j-1]==-1){
par[i][j]=-1;
}
else{
par[i][j]=par[par[i][j-1]][j-1];
}
}
}
for(llo i=0;i<m;i++){
llo aa,bb;
cin>>aa>>bb;
aa--;
bb--;
if(aa==bb){
continue;
}
if(st[aa]>st[bb]){
swap(aa,bb);
}
if(st[bb]>=st[aa] and st[bb]<=endd[aa]){
mm[aa].pb(st[bb]);
u(st[bb]+1,1);
}
else{
pair<llo,pair<llo,llo>> xx=lca(aa,bb);
mm[xx.a].pb(st[aa]);
mm[xx.a].pb(st[bb]);
adj2[par2[xx.b.a]].pb({par2[xx.b.b],1});
adj2[par2[xx.b.b]].pb({par2[xx.b.a],1});
u(st[aa]+1,1);
u(st[bb]+1,1);
}
}
dfs2(0);
llo ans=1;
for(llo i=0;i<n-1;i++){
for(auto j:adj2[i]){
adj2[j.a].pb({i,j.b});
}
}
for(llo i=0;i<n-1;i++){
/*for(auto j:adj2[i]){
cout<<i<<":"<<j.a<<":"<<j.b<<endl;
}*/
if(vis[i]==0){
dfs3(i);
ans=(ans*2)%mod;
}
}
if(ok==0){
cout<<0<<endl;
}
else{
cout<<ans<<endl;
}
//cout<<lca(5,6).a<<","<<lca(5,3).a<<","<<lca(7,1).a<<endl;
/* for(int i=0;i<n;i++){
for(int j=0;j<20;j++){
cout<<par[i][j]<<",";
}
cout<<endl;
}*/
//cout<<lca(5,3).a<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
67448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
397 ms |
142840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
21888 KB |
Output is correct |
| 2 |
Correct |
16 ms |
22144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
21888 KB |
Output is correct |
| 2 |
Correct |
18 ms |
22272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
23424 KB |
Output is correct |
| 2 |
Correct |
18 ms |
23040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
23424 KB |
Output is correct |
| 2 |
Correct |
18 ms |
23040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
532 ms |
118968 KB |
Output is correct |
| 2 |
Correct |
591 ms |
125636 KB |
Output is correct |
| 3 |
Correct |
393 ms |
91056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
741 ms |
140348 KB |
Output is correct |
| 2 |
Correct |
688 ms |
138416 KB |
Output is correct |
| 3 |
Correct |
459 ms |
102192 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
708 ms |
138920 KB |
Output is correct |
| 2 |
Correct |
586 ms |
122052 KB |
Output is correct |
| 3 |
Correct |
520 ms |
101340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
708 ms |
141144 KB |
Output is correct |
| 2 |
Correct |
661 ms |
137592 KB |
Output is correct |
| 3 |
Correct |
456 ms |
93688 KB |
Output is correct |
