/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 300005
#define maxm 500005
#define pii pair <int,int>
#define Task "Usmjeri"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,m,par[maxn][19],h[maxn],lim[maxn],color[maxn];
vector <int> a[maxn];
vector <pair <int,bool> > b[maxn];
void Enter()
{
read(n);read(m);
FOR(i,1,n-1)
{
int x,y;
read(x);
read(y);
a[x].pb(y);
a[y].pb(x);
}
}
void Dfs(int u)
{
for (int v : a[u])
if (par[u][0] != v)
{
par[v][0] = u;
h[v] = h[u] + 1;
FOR(i,1,18) par[v][i] = par[par[v][i-1]][i-1];
Dfs(v);
}
}
int Lca(int u,int v)
{
if (h[u] < h[v]) swap(u,v);
int dis = h[u] - h[v];
FOR(i,0,18)
if ((dis >> i) & 1) u = par[u][i];
if (u == v) return u;
FORD(i,18,0)
if (par[u][i] != par[v][i])
{
u = par[u][i];
v = par[v][i];
}
return par[u][0];
}
void Add_edge(int u,int v,bool cl)
{
b[u].pb(mp(v,cl));
b[v].pb(mp(u,cl));
}
int Paint_Green(int u)
{
for (int v : a[u])
if (v != par[u][0])
{
int temp = Paint_Green(v);
lim[u] = min(lim[u],temp);
if (temp < h[u]) Add_edge(u,v,0);
}
return lim[u];
}
bool Pro(int u,bool cur)
{
if (color[u] != -1) return color[u] == cur;
color[u] = cur;
for (auto v : b[u])
if (!Pro(v.F,cur ^ v.S)) return 0;
return 1;
}
int main()
{
//freopen(Task".inp", "r",stdin);
//freopen(Task".out", "w",stdout);
Enter();
Dfs(h[1] = 1);
FOR(i,1,n) lim[i] = h[i];
while (m--)
{
int x,y;
read(x);read(y);
int c = Lca(x,y);
lim[x] = min(lim[x],h[c]);
lim[y] = min(lim[y],h[c]);
if (c != x && c != y) Add_edge(x,y,1);
}
FOR(i,1,n) color[i] = -1;
Paint_Green(1);
int ans = 1;
FOR(i,2,n)
if (color[i] == -1)
ans = (2 * ans * Pro(i,0)) % maxc;
write(ans);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
128 ms |
37000 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
287 ms |
80128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
80128 KB |
Output is correct |
| 2 |
Correct |
15 ms |
80128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
57 ms |
80128 KB |
Output is correct |
| 2 |
Correct |
14 ms |
80128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
80128 KB |
Output is correct |
| 2 |
Correct |
17 ms |
80128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
80128 KB |
Output is correct |
| 2 |
Correct |
16 ms |
80128 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
372 ms |
80128 KB |
Output is correct |
| 2 |
Correct |
426 ms |
81744 KB |
Output is correct |
| 3 |
Correct |
267 ms |
81744 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
488 ms |
95636 KB |
Output is correct |
| 2 |
Correct |
446 ms |
103424 KB |
Output is correct |
| 3 |
Correct |
328 ms |
103424 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
483 ms |
116664 KB |
Output is correct |
| 2 |
Correct |
467 ms |
120652 KB |
Output is correct |
| 3 |
Correct |
334 ms |
120652 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
515 ms |
137668 KB |
Output is correct |
| 2 |
Correct |
429 ms |
145816 KB |
Output is correct |
| 3 |
Correct |
302 ms |
145816 KB |
Output is correct |
