比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
AAAAAAAAAA |
题目名称 |
Asm.Def的病毒 |
最终得分 |
100 |
用户昵称 |
万千世界,吾为大主宰 |
运行时间 |
0.037 s |
代码语言 |
C++ |
内存使用 |
0.37 MiB |
提交时间 |
2015-11-06 08:42:57 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<deque>
#include<map>
#define ll long long
using namespace std;
int be[1001],en[1001];
int n,q;
struct sd{
int nex,to;
}e[10001];int h[1001],tot=0,no=0;
int fa[1001];
void add(int x,int y){tot++;e[tot].nex=h[x];e[tot].to=y;h[x]=tot;}
void dfs(int x,int faa)
{
be[x]=++no;fa[x]=faa;
for(int i=h[x];i;i=e[i].nex)
{
if(e[i].to!=faa)
{
dfs(e[i].to,x);
}
}
en[x]=++no;
}
bool vis[1001],vis2[1001];
void find1(int x)
{
vis[x]=1;
if(x==1)return;
find1(fa[x]);
}
bool u;
void find2(int x)
{
if(!vis[x])vis[x]=1;
else if(!u)u=1;
else vis[x]=0;
if(x==1)return;
find2(fa[x]);
}
void find3(int x)
{
vis2[x]=1;
if(x==1)return;
find3(fa[x]);
}
bool u2;
void find4(int x)
{
if(!vis2[x])vis2[x]=1;
else if(!u2)u2=1;
else vis2[x]=0;
if(x==1)return;
find4(fa[x]);
}
int main()
{
freopen("asm_virus.in","r",stdin);
freopen("asm_virus.out","w",stdout);
scanf("%d%d",&n,&q);
int x,y,x2,y2;
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
dfs(1,0);
for(int i=1;i<=q;i++)
{
scanf("%d%d%d%d",&x,&y,&x2,&y2);
u=0;u2=0;
memset(vis,0,sizeof vis);
memset(vis2,0,sizeof vis2);
find1(x);find2(y);
find3(x2);find4(y2);
bool p=0;
for(int j=1;j<=n;j++)
if(vis[j]&&vis2[j])
{
p=1;break;
}
if(p)printf("YES\n");
else printf("NO\n");
}
}