比赛 |
“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");
- }
- }