#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1000000001
#define N 300005
#define LOG 20
#define magic 100
#define MAX 1000005
#define KOK 350
#define EPS 0.000000000001
#define pw(x) 1ll*((1ll)<<(x))
#define PI 3.1415926535
using namespace std;
int baba[LOG+2][N],der[N],anc[N],way[N];
int x,y,n,m,C;
vector<int> v[N];
int bul(int node) {
if(anc[node]==node) return node;
return anc[node]=bul(anc[node]);
}
int lca(int x,int y) {
if(der[x]<der[y]) swap(x,y);
int dx=der[x];
for(int i=LOG-1;i>=0;i--) {
if(dx-pw(i)>=der[y]) {
dx-=pw(i);
x=baba[i][x];
}
}
if(x==y) return x;
for(int i=LOG-1;i>=0;i--) {
if(baba[i][x]!=baba[i][y]) {
x=baba[i][x];
y=baba[i][y];
}
}
return baba[0][x];
}
void build_lca() {
for(int i=1;i<LOG;i++) {
for(int j=1;j<=n;j++) {
baba[i][j]=baba[i-1][baba[i-1][j]];
}
}
}
void fail() {printf("0");exit(0);}
int make_up(int x,int to,int wyx) {
if(x==to || way[x]) {
if(x!=to && way[x]!=wyx) fail();
if(x!=to) return bul(x);
return -1;
}
way[x]=wyx;
int par=make_up(baba[0][x],to,wyx);
if(par==-1) par=bul(x);
if(par!=bul(x)) C--;
anc[bul(x)]=par;
return par;
}
int go_up(int x,int to) {
while(x!=to) {
if(way[x]) return way[x];
x=baba[0][x];
}
return 0;
}
void dfs1(int node,int ata) {
baba[0][node]=ata;
der[node]=der[ata]+1;
for(int i:v[node]) {
if(i==ata) continue ;
dfs1(i,node);
}
}
int main() {
#if 0
freopen("input.txt","r",stdin);
#endif
scanf("%d %d",&n,&m);
for(int i=2;i<=n;i++) anc[i]=i;
C=n-1;
for(int i=1;i<n;i++) {
scanf("%d %d",&x,&y);
v[x].pb(y);
v[y].pb(x);
}
dfs1(1,0);
build_lca();
while(m--) {
scanf("%d %d",&x,&y);
int _lca=lca(x,y);
int way1=go_up(x,_lca);
if(!way1) {
way1=3-go_up(y,_lca);
if(way1==3) {
way1=1;
}
}
int dad1=make_up(x,_lca,way1);
int dad2=make_up(y,_lca,3-way1);
if(bul(dad1)!=bul(dad2) && ~dad1 && ~dad2) {
C--;
anc[bul(dad1)]=bul(dad2);
}
}
int ans=1;
for(int i=1;i<=C;i++) ans=ans*2%MOD;
printf("%d\n",ans);
}
Compilation message
usmjeri.cpp: In function 'int main()':
usmjeri.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
usmjeri.cpp:176:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
usmjeri.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&x,&y);
~~~~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
132 ms |
24056 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
266 ms |
56908 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
8 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
14 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
11 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
377 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
426 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
445 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
492 ms |
56908 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
