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）