第一行包含三个正整数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.net/101426.html原文链接：https://javaforall.net
