第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。
接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。
输出格式:
输出包含M行,每行包含一个正整数,依次为每一个询问的结果。
输入样例#1:
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出样例#1:
4
4
1
4
4
模板:时间复杂度nlogn
#include<iostream>
#include<cstdio>
using namespace std;
struct yyy{
int t,
nex;
}e[2 * 500001];
int deepth[500001], fa[500001][22], lg[500001], head[500001];
int tot;
void add(int x, int y) //邻接表存树
{
e[++tot].t = y;
e[tot].nex = head[x];
head[x] = tot;
}
void dfs(int f, int fath)
{
deepth[f] = deepth[fath] + 1;
fa[f][0] = fath;
for (int i = 1; (1 << i) <= deepth[f]; i++)
fa[f][i] = fa[fa[f][i - 1]][i - 1];
for (int i = head[f]; i; i = e[i].nex)
if (e[i].t != fath)
dfs(e[i].t, f);
}
int lca(int x, int y)
{
if (deepth[x]<deepth[y])
swap(x, y);
while (deepth[x]>deepth[y])
x = fa[x][lg[deepth[x] - deepth[y]] - 1];
if (x == y)
return x;
for (int k = lg[deepth[x]]; k >= 0; k--)
if (fa[x][k] != fa[y][k])
x = fa[x][k], y = fa[y][k];
return fa[x][0];
}
int n, m, s;//n节点,m查询,s边数
void init()
{
scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i <= n - 1; i++)
{
int x, y; scanf("%d%d", &x, &y);
add(x, y); add(y, x);
}
dfs(s, 0);
for (int i = 1; i <= n; i++)
lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
}
int main()
{
init();
for (int i = 1; i <= m; i++)
{
int x, y; scanf("%d%d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}
转载于:https://www.cnblogs.com/ALINGMAOMAO/p/9643481.html
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/101426.html原文链接: