首页 > 代码库 > COGS 2098. Asm.Def的病毒
COGS 2098. Asm.Def的病毒
★☆ 输入文件：asm_virus.in 输出文件：asm_virus.out 简单对比
时间限制：1 s 内存限制：256 MB
【题目描述】
“这就是我们最新研制的，世界上第一种可持久化动态计算机病毒，‘创世纪’。”方教授介绍道。
“哦。”主席面无表情地点点头。
“‘创世纪’无法真正杀死透明计算网络，但是可以把它变成傻子。可惜透明计算网络能轻松地辨认出病毒，所以我建议……”
“为什么不伪装呢？”Asm.Def说。
“当然不行，它比我们更懂伪装。”
“我是说，把我们的病毒伪装成杀毒软件。”
方教授震惊地盯着Asm.Def看了一会。“你是个天才。”
Asm.Def想把病毒伪装成杀毒软件，入侵透明计算网络。透明计算网络的文件结构是一棵N个节点的树，每个病毒可以入侵一条路径上的所有节点。但如果两个病毒入侵了同一个节点，由于它们伪装成了杀毒软件，就会自相残杀。Asm.Def不希望这样的情况发生，所以他需要仔细制定入侵计划。为此，他需要频繁地询问，两条路径是否经过同一个节点（即是否相交）。
【输入格式】
第一行两个整数N,Q。
接下来N-1行，每行两个整数a,b，表示(a,b)是树上的一条边。
接下来Q行，每行四个整数s1,t1,s2,t2，表示询问s1~t1的路径是否与s2~t2的路径相交。
【输出格式】
对每个询问，若相交则输出一行”YES”，否则输出一行”NO”。
【样例输入】
6 51 21 32 44 54 61 1 5 61 2 6 32 3 5 66 4 3 14 3 1 2
【样例输出】
NOYESNONOYES
【提示】
N,Q<=1000.
1<=s1,t1,s2,t2<=N。
【来源】
在此键入。
倍增求LCA
屠龙宝刀点击就送
#include <ctype.h>#include <cstdio>#define M 1005void read(int &x){ x=0; bool f=0; char ch=getchar(); while(!isdigit(ch)) {if(ch==‘-‘) f=1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-‘0‘;ch=getchar();} x=f?(~x)+1:x;}struct node{ int next,to; node(int next=0,int to=0) :next(next),to(to){}}edge[M<<2];int head[M],cnt,dad[M][25],dep[M],N,Q;void add(int u,int v){ edge[++cnt]=node(head[u],v); head[u]=cnt;}void dfs(int x){ dep[x]=dep[dad[x][0]]+1; for(int i=0;dad[x][i];i++) dad[x][i+1]=dad[dad[x][i]][i]; for(int i=head[x];i;i=edge[i].next) { if(dad[x][0]!=edge[i].to) { dad[edge[i].to][0]=x; dfs(edge[i].to); } }}int max(int a,int b) {return a>b?a:b;}void swap(int &x,int &y){ int tmp=y; y=x; x=tmp;}int lca(int x,int y){ if(dep[x]>dep[y]) swap(x,y); for(int i=20;i>=0;i--) if(dep[dad[y][i]]>=dep[x]) y=dad[y][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(dad[x][i]!=dad[y][i]) x=dad[x][i],y=dad[y][i]; return dad[x][0];}int main(){ freopen("asm_virus.in","r",stdin); freopen("asm_virus.out","w",stdout); read(N); read(Q); for(int x,y,i=1;i<N;i++) { read(x); read(y); add(x,y); add(y,x); } dfs(1); for(int a,b,c,d;Q--;) { read(a);read(b); read(c);read(d); int maxn=0; maxn=max(lca(a,b),lca(c,d)); if(lca(a,c)>=maxn||lca(a,d)>=maxn||lca(b,c)>=maxn||lca(b,d)>=maxn) printf("YES\n"); else printf("NO\n"); } return 0;}
COGS 2098. Asm.Def的病毒
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。