luogu 3398 仓鼠找sugar (LCA 在线倍增)

本文主要是介绍luogu 3398 仓鼠找sugar (LCA 在线倍增)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！

 

输入输出格式

输入格式：

第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。

输出格式：

对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。

 

输入输出样例

输入样例#1：

5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4

输出样例#1：

Y
N
Y
Y
Y

说明

本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。

20%的数据 n<=200,q<=200

40%的数据 n<=2000,q<=2000

70%的数据 n<=50000,q<=50000

100%的数据 n<=100000,q<=100000

题目链接：https://www.luogu.org/problemnew/show/P3398

题目分析：设a，b点的lca为lcaAB；c，d点的lca为lcaCD，则若deep[lcaAB]<deep[c]且deep[lcaAB]<deep[d]，答案显然是N，lcaCD对应的情况同理，即某两点的lca的深度比剩余另外两点都要大。否则，不妨先假设lcaAB>lcaCD，因为a，b点的最近公共祖先更深，如果可以相遇必然要满足c点到d点的路径包含lcaAB，那么对lcaAB和c，lcaAB和d再求两次lca，若求出的值就是lcaAB自身，则满足条件，lcaAB<=lcaCD的情况同理

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const POW = 22;
int const MAX = 100005;int head[MAX], cnt;
int n, q, dep[MAX], p[MAX][25];struct EDGE {int to, nxt;
}e[MAX << 1];void Init() {cnt = 0;memset(head, -1, sizeof(head));
}void Add(int u, int v) {e[cnt].to = v;e[cnt].nxt = head[u];head[u] = cnt++;
}void DFS(int u, int fa) {dep[u] = dep[fa] + 1;p[u][0] = fa;for (int i = 1; i <= POW; i++) {p[u][i] = p[p[u][i - 1]][i - 1];}for (int i = head[u]; i != -1; i = e[i].nxt) {int v = e[i].to;if (v != fa) {DFS(v, u);}}
}int LCA(int u, int v) {if (dep[u] < dep[v]) {swap(u, v);}int diff = dep[u] - dep[v];for (int i = POW; i >= 0; i--) {if (diff & (1 << i)) {u = p[u][i];}}if (u == v) {return u;}for (int i = POW; i >= 0; i--) {if (p[u][i] != p[v][i]) {u = p[u][i];v = p[v][i];}}return p[u][0];
}int main() {Init();int u, v;scanf("%d %d", &n, &q);for (int i = 1; i < n; i++) {scanf("%d %d", &u, &v);Add(u, v);Add(v, u);} DFS(1, 0);int a, b, c, d;while (q--) {scanf("%d %d %d %d", &a, &b, &c, &d);int lcaAB = LCA(a, b);int lcaCD = LCA(c, d);if (dep[lcaAB] > dep[c] && dep[lcaAB] > dep[d]) {printf("N\n");} else if (dep[lcaCD] > dep[a] && dep[lcaCD] > dep[b]) {printf("N\n");} else {if (dep[lcaAB] > dep[lcaCD]) {printf("%c\n", (LCA(c, lcaAB) == lcaAB || LCA(d, lcaAB) == lcaAB) ? 'Y' : 'N');} else {printf("%c\n", (LCA(a, lcaCD) == lcaCD || LCA(b, lcaCD) == lcaCD) ? 'Y' : 'N');}}}
}

 

这篇关于luogu 3398 仓鼠找sugar (LCA 在线倍增)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---