C. cltt的幸运数LCAdfs

时间:2022-03-30 12:25:25

/*C: cltt的幸运数

Time Limit: 1 s      Memory Limit: 128 MB

Submit

Problem Description

一棵树有n个节点,共m次查询,查询a,b的最近公共祖先是否为好数?若好数的数目是幸运数,输出YES,否则输出NO。

好数:可以表示为2的指数幂。如:1, 2,4,8,16,32,……

幸运数就是素数。

Input

nn(nn表示节点数目,接下来n−1n−1行,每行两个整数 x,yx,y 其中xx是yy的父节点)

mm(表示查询数目,接下来mm行,每行两个整数a,ba,b)

(1≤n≤105,1≤m≤10)(1≤n≤105,1≤m≤10)

Output

YESYES or NONO

Sample Input

12

1 2

1 3

2 5

3 4

3 6

4 7

7 9

7 10

6 8

8 11

8 12

4

9 8

4 7

11 12

10 7

Sample Output

YES*/

#include<iostream>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>v[111111];
vector<int>p[111111];
bool vis[111111];
int cnt,pre[111111];
int res=0;
int ret[111111];
int find(int pos)
{
return pre[pos]=pre[pos]==pos?pos:find(pre[pos]);
}
bool check(int x)
{
if(x==1||x==0)return 0;//有可能为0
if(x==2)return 1;
for(int i=2;i*i<=x;i++)
if(x%i==0)
return 0;
return 1;
}
void dfs(int er,int fu)//顺序:每走一个节点找一次关系节点
{
vis[er]=1;
int num=p[er].size();
for(int i=0;i<num;i++)//此过程先进行,防止最近公共祖先为同一链上的节点影响
{
int pos=p[er][i];
if(vis[pos])
{
int ans=find(pos);
ret[res++]=ans;
//不能找一个查一个,
//因为可能有些就不存在最近公共祖先,认为是0
//因此为了这种特殊情况,为了你们比赛时避免判断的干扰。
//后台把0也当作了好数
}
}
num=v[er].size();
for(int i=0;i<num;i++)
{
int pos=v[er][i];
dfs(pos,er);
}
pre[er]=fu;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<=n;i++)
{ pre[i]=i;
}
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
vis[y]=1;//有父亲
}
int o,head; scanf("%d",&o); cnt=0;
for(int i=0;i<o;i++)
{
int x,y;
scanf("%d%d",&x,&y);
p[x].push_back(y);
p[y].push_back(x);
}
for(int i=1;i<=n;i++)
{
if(vis[i]==0)
{
head=i;
break;
}
}
memset(vis,0,sizeof(vis));
dfs(head,-1);//cout<<res<<endl;
for(int i=0;i<o;i++){
if(!(ret[i]&(ret[i]-1)))//0&(-1)==0,
cnt++;//要全部找到后再一个一个的判断
}
/*
以后判断2的指数幂时要 x!=0&&x&(x-1)==0 才可以
*/
if(check(cnt))
printf("YES\n");
else
printf("NO\n");
return 0;
}