首页 > 代码库 > COGS——C2098. Asm.Def的病毒
COGS——C2098. Asm.Def的病毒
http://www.cogs.pro/cogs/problem/problem.php?pid=2098
★☆ 输入文件：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。
【来源】
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int N(1000+15); 7 int n,q,u,v; 8 9 int head[N],sumedge;10 struct Edge11 {12 int v,next;13 Edge(int v=0,int next=0):14 v(v),next(next){}15 }edge[N<<1];16 void ins(int u,int v)17 {18 edge[++sumedge]=Edge(v,head[u]);19 head[u]=sumedge;20 }21 22 int dad[N],size[N],deep[N],top[N];23 void DFS(int x)24 {25 size[x]=1;deep[x]=deep[dad[x]]+1;26 for(int i=head[x];i;i=edge[i].next)27 {28 int v=edge[i].v;29 if(dad[x]==v) continue;30 dad[v]=x; DFS(v); size[x]+=size[v];31 }32 }33 void DFS_(int x)34 {35 int t=0; if(!top[x]) top[x]=x;36 for(int i=head[x];i;i=edge[i].next)37 {38 int v=edge[i].v;39 if(dad[x]!=v&&size[t]<size[v]) t=v;40 }41 if(t) top[t]=top[x],DFS_(t);42 for(int i=head[x];i;i=edge[i].next)43 {44 int v=edge[i].v;45 if(dad[x]!=v&&v!=t) DFS_(v);46 }47 }48 int LCA(int x,int y)49 {50 for(;top[x]!=top[y];x=dad[top[x]])51 if(deep[top[x]]<deep[top[y]]) swap(x,y);52 return deep[x]<deep[y]?x:y;53 }54 55 int main()56 {57 freopen("asm_virus.in","r",stdin);58 freopen("asm_virus.out","w",stdout);59 60 scanf("%d%d",&n,&q);61 for(int i=1;i<n;i++)62 scanf("%d%d",&u,&v),ins(u,v),ins(v,u);63 DFS(1); DFS_(1);64 for(int uu,vv;q--;)65 {66 scanf("%d%d%d%d",&u,&v,&uu,&vv);67 int lca=LCA(u,v),lcaa=LCA(uu,vv);68 if(deep[lca]<deep[lcaa])69 swap(lca,lcaa),swap(u,uu),swap(v,vv);70 if(LCA(lca,uu)==lca||LCA(lca,vv)==lca)71 puts("YES");72 else puts("NO");73 }74 return 0;75 }
COGS——C2098. Asm.Def的病毒
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。