比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
WWWWWWWWWW |
题目名称 |
Asm.Def的病毒 |
最终得分 |
0 |
用户昵称 |
Fmuckss |
运行时间 |
0.475 s |
代码语言 |
C++ |
内存使用 |
4.22 MiB |
提交时间 |
2015-11-06 10:45:41 |
显示代码纯文本
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define maxn 1005
using namespace std;
int n,q;
int lca[maxn][maxn];
int fa[maxn],anc[maxn];
bool vis1[maxn],vis2[maxn];
vector<int> qx[maxn];
void beg(int x){
for(int i=1;i<=x;i++){
fa[i]=i;
anc[i]=i;
vis1[i]=false;
vis2[i]=false;
}
}
int findfa(int a){
return fa[a]=(fa[a]==a ? a:findfa(fa[a]));
}
void unionab(int a,int b){
int faa=findfa(a),fba=findfa(b);
if(faa!=fba){
fa[a]=fba;
}
}
struct que{
int x1,y1,x2,y2;
bool l;
}qs[maxn];
struct node{
vector<int> ne;
}ns[maxn];
void tarjan(int i){
vis1[i]=true;
for(int j=0;j<ns[i].ne.size();j++){
if(vis1[ns[i].ne[j]])continue;
tarjan(ns[i].ne[j]);
unionab(i,ns[i].ne[j]);
anc[findfa(i)]=i;
}
vis2[i]=true;
for(int j=0;j<qx[i].size();j++){
if(vis2[qx[i][j]]){
lca[i][qx[i][j]]=anc[findfa(qx[i][j])];
lca[qx[i][j]][i]=lca[i][qx[i][j]];
}
}
}
void solve(){
for(int i=1;i<=n;i++){
beg(n);
tarjan(i);
for(int i=1;i<=q;i++){
int x1=qs[i].x1,x2=qs[i].x2;
int y1=qs[i].y1,y2=qs[i].y2;
if(lca[x1][y1]==lca[x2][y2]){
qs[i].l=true;
}
}
}
for(int i=1;i<=q;i++){
if(qs[i].l){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
void read(){
scanf("%d %d",&n,&q);
for(int i=1;i<=n-1;i++){
int a,b;
scanf("%d %d",&a,&b);
ns[a].ne.push_back(b);
ns[b].ne.push_back(a);
}
for(int i=1;i<=q;i++){
int x1,y1,x2,y2;
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
qx[x1].push_back(y1);
qx[x2].push_back(y2);
qx[y1].push_back(x1);
qx[y2].push_back(x2);
qs[i].x1=x1;qs[i].x2=x2;
qs[i].y1=y1;qs[i].y2=y2;
}
}
int main(){
freopen("asm_virus.in","r",stdin);
freopen("asm_virus.out","w",stdout);
read();
solve();
return 0;
}