#include <bits/stdc++.h>
using namespace std;
//DSU
int mn1 = 300001;
int pr1[300001],pr2[300001];
int gs1[300001],gs2[300001];
int findleader1(int x){
if(pr1[x]==x){
return x;
}
return pr1[x] = findleader1(pr1[x]);
}
bool samegroup1(int x,int y){
int led1 = findleader1(x);
int led2 = findleader1(y);
return led1==led2;
}
void mergegroup1(int x,int y){
int led1 = findleader1(x);
int led2 = findleader1(y);
if(led1==led2)return;
if(gs1[led1]>gs1[led2]){
pr1[led2]=led1;
gs1[led1]+=gs1[led2];
}else{
pr1[led1]=led2;
gs1[led2]+=gs1[led1];
}
}
int findleader2(int x){
if(pr2[x]==x){
return x;
}
return pr2[x] = findleader2(pr2[x]);
}
bool samegroup2(int x,int y){
int led1 = findleader2(x);
int led2 = findleader2(y);
return led1==led2;
}
void mergegroup2(int x,int y){
int led1 = findleader2(x);
int led2 = findleader2(y);
if(led1==led2)return;
if(gs2[led1]>gs2[led2]){
pr2[led2]=led1;
gs2[led1]+=gs2[led2];
}else{
pr2[led1]=led2;
gs2[led2]+=gs2[led1];
}
}
int dep[300001];
int P[300001][20];
int ed[300001];
int lca(int x,int y)
{
if(dep[x]<dep[y]) swap(x,y);
for(int k=19;k>=0;k--)
{
if(dep[x]-(1<<k) >= dep[y])
x=P[x][k];
}
if(x==y) return x;
for(int k=19;k>=0;k--)
{
if(P[x][k] != P[y][k])
x=P[x][k],y=P[y][k];
}
return P[x][0];
}
vector<pair<int,int>> adj[300001];
void dfs(int i,int pr,int e){
P[i][0] = pr;
ed[i] = e;
dep[i] = dep[pr]+1;
for(int j = 1;j<20;j++){
P[i][j] = P[P[i][j-1]][j-1];
}
for(auto j:adj[i]){
if(j.first!=pr){
dfs(j.first,i,j.second);
}
}
}
vector<int> e[300001];
int vis[300001] , col[300001];
bool ss = 1;
void color(int i,int c){
vis[i] = 1;col[i] = c;
for(auto j:e[i]){
if(vis[j]==0){
color(j,!c);
}else{
if(col[j]==c){
ss = 0;
}
}
}
}
int main(){
//freopen("poklonin6.txt","r",stdin);
for(int i = 0;i<mn1;i++){
pr1[i] = i , pr2[i] = i , gs1[i] = 1, gs2[i] = 1;
}
int n,m;
cin>>n>>m;
for(int i = 0;i<n-1;i++){
int a,b;cin>>a>>b;
adj[a].push_back({b,i});
adj[b].push_back({a,i});
}
dfs(1,0,0);
while(m--){
int a,b;cin>>a>>b;
int lc = lca(a,b);
int cur = a , last = -1;
if(dep[a]>dep[lc]){
last = ed[a];
}
while(dep[cur]>dep[lc]){
for(int j = 19;j>=0;j--){
if(samegroup1(cur,P[cur][j])){
cur = P[cur][j];
}
}
if(dep[cur]>dep[lc]){
mergegroup1(cur,P[cur][0]);
mergegroup2(last,ed[cur]);
}
cur = P[cur][0];
if(dep[cur]>dep[lc]){
mergegroup2(last,ed[cur]);
}
}
int last2 = last;
swap(a,b);
cur = a , last = -1;
if(dep[a]>dep[lc]){
last = ed[a];
}
while(dep[cur]>dep[lc]){
for(int j = 19;j>=0;j--){
if(samegroup1(cur,P[cur][j])){
cur = P[cur][j];
}
}
if(dep[cur]>dep[lc]){
mergegroup1(cur,P[cur][0]);
mergegroup2(last,ed[cur]);
}
cur = P[cur][0];
if(dep[cur]>dep[lc]){
mergegroup2(last,ed[cur]);
}
}
if(last!=-1&&last2!=-1){
e[findleader2(last)].push_back(findleader2(last2));
e[findleader2(last2)].push_back(findleader2(last));
}
}
long long ans = 1;
for(int i = 0;i<n-1;i++){
if(!vis[findleader2(i)]){
color(findleader2(i),0);
ans*=2;ans%=(1000000007);
}
}
if(!ss){
cout<<"0\n";
}else cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
36116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
541 ms |
73504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19156 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
19876 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
19728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
669 ms |
62640 KB |
Output is correct |
| 2 |
Correct |
661 ms |
67080 KB |
Output is correct |
| 3 |
Correct |
307 ms |
49948 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
691 ms |
64456 KB |
Output is correct |
| 2 |
Correct |
642 ms |
68508 KB |
Output is correct |
| 3 |
Incorrect |
444 ms |
51936 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
719 ms |
64584 KB |
Output is correct |
| 2 |
Correct |
648 ms |
66836 KB |
Output is correct |
| 3 |
Correct |
410 ms |
52028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
611 ms |
65720 KB |
Output is correct |
| 2 |
Incorrect |
640 ms |
68888 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
