#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<int>adj[300005];
vector<ii>input;
map<ii,int> edge;
vector<ii>arr(300005);
vector<int>no(300005),path(300005,0);
vector<int>depth(300005,0),edgedepth(300005,0);
vector<vector<int>> anc(20,vector<int>(300005,0));
int lca(int x,int y){
if(depth[x]<depth[y])swap(x,y);
while(depth[x]!=depth[y]){
x=anc[log2(depth[x]-depth[y])][x];
}
if(x==y)return x;
while(anc[0][x]!=anc[0][y]){
int w=19;
while(anc[w][x]==anc[w][y])w--;
x=anc[w][x];
y=anc[w][y];
}
return anc[0][x];
}
int F(int x){
if(no[x]==x)return x;
return no[x]=F(no[x]);
}
bool merge(int x,int y){
x=F(x);
y=F(y);
if(x==y)return false;
if(edgedepth[x]>edgedepth[y])swap(x,y);
no[y]=x;
return true;
}
void dfs(int x,int pre,int d){
depth[x]=d;
for(int i=0;i<adj[x].size();i++){
int y=adj[x][i];
if(y==pre)continue;
anc[0][y]=x;
edgedepth[edge[{x,y}]]=d;
dfs(y,x,d+1);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int n,m;
cin>>n>>m;
for(int i=1;i<=n-1;i++)no[i]=i;
for(int i=1;i<=n;i++)path[i]=i;
for(int i=0;i<n-1;i++){
int x,y;cin>>x>>y;
adj[x].pb(y);
adj[y].pb(x);
edge[{x,y}]=i+1;
edge[{y,x}]=i+1;
arr[i+1]={x,y};
}
dfs(1,0,0);
for(int d=1;d<20;d++){
for(int x=1;x<=n;x++)anc[d][x]=anc[d-1][anc[d-1][x]];
}
int ans=1;
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
if(depth[x]<depth[y])swap(x,y);
input.pb({x,y});
int l=lca(x,y);
if(depth[path[x]]>depth[l])path[x]=l;
if(depth[path[y]]>depth[l])path[y]=l;
}
for(int i=1;i<=n;i++){
int x=i;
if(x==path[x])continue;
int finish=path[x];
int last=edge[{x,anc[0][x]}];
x=anc[0][x];
while(depth[x]>depth[finish]){
if(merge(edge[{x,anc[0][x]}],last)){
last=edge[{x,anc[0][x]}];
x=anc[0][x];
}
else{
int q=arr[F(last)].first,w=arr[F(last)].second;
if(depth[q]<depth[w])swap(q,w);
last=edge[{q,w}];
x=w;
}
}
}
for(int i=0;i<m;i++){
int x=input[i].first,y=input[i].second;
int l=lca(x,y);
if(y==l)continue;
if(F(edge[{x,anc[0][x]}])==F(edge[{y,anc[0][y]}]))ans=0;
}
for(int i=0;i<m;i++){
int x=input[i].first,y=input[i].second;
int l=lca(x,y);
if(y==l)continue;
///direction is ignored
}
for(int i=0;i<m;i++){
int x=input[i].first,y=input[i].second;
int l=lca(x,y);
if(y==l)continue;
merge(edge[{x,anc[0][x]}],edge[{y,anc[0][y]}]);
}
set<int> cnt;
for(int i=1;i<=n-1;i++)cnt.insert(F(i));
for(int i=0;i<cnt.size();i++)ans=ans*2%modulo;
cout<<ans<<endl;
}
Compilation message
usmjeri.cpp: In function 'void dfs(long long int, long long int, long long int)':
usmjeri.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
usmjeri.cpp: In function 'int32_t main()':
usmjeri.cpp:124:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<cnt.size();i++)ans=ans*2%modulo;
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
662 ms |
106420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1373 ms |
173744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
70776 KB |
Output is correct |
| 2 |
Correct |
66 ms |
70780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
70776 KB |
Output is correct |
| 2 |
Correct |
66 ms |
70776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
74 ms |
70776 KB |
Output is correct |
| 2 |
Correct |
72 ms |
70776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
76 ms |
70808 KB |
Output is correct |
| 2 |
Correct |
71 ms |
70780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2028 ms |
139048 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2059 ms |
133876 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2054 ms |
134480 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2057 ms |
134912 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
