#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<int>no(300005),direct(300005,-1);
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=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;
input.pb({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);
int last=edge[{x,anc[0][x]}];
int l=lca(x,y);
x=anc[0][x];
while(x!=l){
merge(last,edge[{x,anc[0][x]}]);
last=edge[{x,anc[0][x]}];
x=anc[0][x];
}
if(y==l)continue;
last=edge[{y,anc[0][y]}];
y=anc[0][y];
while(l!=y){
merge(last,edge[{y,anc[0][y]}]);
last=edge[{y,anc[0][y]}];
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;
}
Compilation message
usmjeri.cpp: In function 'void dfs(long long int, long long int, long long int)':
usmjeri.cpp:45: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:97: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 |
Execution timed out |
2023 ms |
94988 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2102 ms |
157168 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
66108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
66008 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
70 ms |
66076 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
71 ms |
66016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2027 ms |
121736 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2016 ms |
121824 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
122364 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2049 ms |
122684 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
