★☆ 输入文件：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 5 1 2 1 3 2 4 4 5 4 6 1 1 5 6 1 2 6 3 2 3 5 6 6 4 3 1 4 3 1 2
NO YES NO NO YES
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 Edge 11 { 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 }
原文：http://www.cnblogs.com/Shy-key/p/7197646.html