题目链接：http://cogs.pro:8081/cogs/problem/problem.php?pid=vQXmxVaPU
“这就是我们最新研制的，世界上第一种可持久化动态计算机病毒，‘创世纪’。”方教授介绍道。
“哦。”主席面无表情地点点头。
“‘创世纪’无法真正杀死透明计算网络，但是可以把它变成傻子。可惜透明计算网络能轻松地辨认出病毒，所以我建议……”
“为什么不伪装呢？”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。
#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <cstdio> #include <cstring> #define MAXN 1010 using namespace std; struct edge { int to; edge* pre; edge() :to(0), pre(NULL) {}; }e[MAXN << 1]; int n, q; int s1, t1, s2, t2; int a, b, cnt = 0; edge* preV[MAXN] = { NULL }; //preV[n]用于取以n为起点的边的地址，依次更新，如果链式遍历每个以n为起点的边 int p[MAXN] = { 0 }; //p[n] 为n的父亲节点 bool vis[MAXN << 1]; void insert(int a, int b) { e[cnt].to = b; e[cnt].pre = preV[a]; preV[a] = &e[cnt++]; } void dfs(int x) //遍历处理p数组 { int y; for (edge* ee = preV[x]; ee; ee = ee->pre) { y = ee->to; if (y == p[x]) continue ; p[y] = x; dfs(y); } } int LCA(int x, int y) //找到x和y的lca { memset(vis, 0, sizeof(vis)); while (x) { vis[x] = true; x = p[x]; } while (y) { if(vis[y]) return y; y = p[y]; } return x; } int query(int lca, int s, int t) //查询lca是否在s和t的路径上 { int l = LCA(s, t); do { if (lca == s) //判断是否lca就是节点s return true; if (s == l) //判断节点s是否是s和t的lca break; s = p[s]; //往上走 } while (s); /*不能用while的原因是：如果s刚好就等于L，无法进入循环，就无法对于lca==s返回true，如果将s==l放后边，则s = p[s]就把s转移了*/ while (t && t != l) { if (lca == t) return true; t = p[t]; } return false; } int main() { //freopen("asm_virus.in", "r", stdin); //freopen("asm_virus.out", "w", stdout); scanf("%d %d", &n, &q); for (int i = 1; i < n; i++) { scanf("%d %d", &a, &b); insert(a, b); insert(b, a); } dfs(1); int firLCA, secLCA; while (q--) { scanf("%d %d %d %d", &s1, &t1, &s2, &t2); firLCA = LCA(s1, t1); secLCA = LCA(s2, t2); if (query(firLCA, s2, t2) || query(secLCA, s1, t1)) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }
LCA -cogs2098 [SYOI 2015] Asm.Def的病毒
原文：https://www.cnblogs.com/kxxy/p/11740532.html