CSU 1079: 树上的查询 （LCA最近公共祖先问题）
【摘要】
题目：
Description
现有一棵有N个顶点的树，顶点的标号分别为1, 2, …, N。对于每个形如a b k的询问，你需要回答在从点a到点b的路径上是否包含点k。
Input
输入包含多组测试数据。
对于每组测试数据，第一行包含两个正整数N, Q (1<=N, Q<=10^5)，分别表示这棵树一共有...
题目：
Input
输入包含多组测试数据。
对于每组测试数据，第一行包含两个正整数N, Q (1<=N, Q<=10^5)，分别表示这棵树一共有N个顶点，接下来你需要回答Q个询问。接下来N-1行中，第i行描述了这棵树的第i条边：包含两个正整数xi、yi，表示点xi和点yi之间有一条无向边。再接下来一共Q行，每行均包含三个正整数a、b、k (1<=a, b, k<=N)，表示你需要回答在从点a到点b的路径上是否包含点k。
Output
对于每组测试数据，你需要按顺序依次回答每个询问。对于任意一个询问a b k，如果点a到点b的路径上包含点k，则输出“YES”（不包括引号），否则输出“NO”（不包括引号）。每组数据结尾输出一个空行。
就是简单的LCA问题，关于LCA参考我的另外一篇博客：HDU 2586 How far away？（LCA使用详解）
代码：
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int n;
vector<int>v[100001];//存儿子标号
int deep[100001];//每个点的深度
int visitnum[200001];//遍历数是2*n-1
int visitn[100001];//每个点的任意一个遍历数
int vnum;
int mins[200001][20]; //区间最小值
int fa[100001];
void visit(int m, int d) //遍历重编号
{
vector<int>::iterator p;
deep[m] = d;
for (p = v[m].begin(); p != v[m].end(); p++)
{
if (fa[*p]>-1)continue;
fa[*p] = m;
visitnum[vnum++] = m; //存入访问的第vnum个点是哪个点
visit(*p, d + 1);
}
visitn[m] = vnum; //注意这2句的顺序
visitnum[vnum++] = m;
}
void rmq() //计算区间最小值
{
for (int i = 1; i <= 2 * n - 1; i++)mins[i][0] = visitnum[i];
for (int j = 1; (1 << j) <= 2 * n - 1; j++)
{
for (int i = 1; i <= 2 * n - 1; i++)
{
mins[i][j] = mins[i][j - 1];
int k = i + (1 << (j - 1));
if (k <= 2 * n - 1 && deep[mins[i][j]] > deep[mins[k][j - 1]])
mins[i][j] = mins[k][j - 1];
}
}
}
int lca(int x, int y) //求最近公共祖先
{
x = visitn[x], y = visitn[y];
if (x > y)x ^= y ^= x ^= y;
int j = 0;
while ((1 << j) <= y - x + 1)j++;
j--;
int min = mins[y + 1 - (1 << j)][j];
if (deep[min] > deep[mins[x][j]])min = mins[x][j];
return min;
}
int main()
{
int q, x, y, k;
bool fl = false;
while (scanf("%d%d", &n, &q) != EOF)
{
if (fl)printf("\n");
fl = true;
vnum = 1;
for (int i = 1; i <= n; i++)
{
v[i].clear(); //初始化
fa[i] = -1;
}
for (int i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
v[x].insert(v[x].end(), y);//存入儿子的标号
v[y].insert(v[y].end(), x);//存入儿子的标号
}
fa[1] = 1;
visit(1, 1);
rmq();
while (q--)
{
scanf("%d%d%d", &x, &y, &k);
int lca1 = lca(x, y), lca2 = lca(x, k), lca3 = lca(y, k);
bool flag = (lca1 == lca2 && lca3 == k);
if (lca1 == lca3 && lca2 == k)flag = true;
if (flag)printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/79775935
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）