《P3398 仓鼠找 sugar》

题目描述

小仓鼠的和他的基（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,q≤200。

40% 的数据 n,q≤2×103。

70% 的数据 n,q≤5×104。

100% 的数据 1≤n,q≤105。

代码实现：

#include<bits/stdc++.h>
using namespace std;

const int MAX_NODE = 100010;
int f[MAX_NODE][25], depth[MAX_NODE], distance[MAX_NODE];
int logLevel, totalNodes, totalQueries, edgeCount;
int adjVer[2*MAX_NODE], adjNext[2*MAX_NODE], adjHead[MAX_NODE];
queue<int> bfsQueue;

void addEdge(int fromNode, int toNode) {
adjVer[++edgeCount] = toNode;
adjNext[edgeCount] = adjHead[fromNode];
adjHead[fromNode] = edgeCount;
}

int findLCA(int nodeA, int nodeB) {
if (depth[nodeA] > depth[nodeB]) {
swap(nodeA, nodeB);
}
for (int k = logLevel; k >= 0; k--) {
if (depth[f[nodeB][k]] >= depth[nodeA]) {
nodeB = f[nodeB][k];
}
}
if (nodeA == nodeB) {
return nodeA;
}
for (int k = logLevel; k >= 0; k--) {
if (f[nodeA][k] != f[nodeB][k]) {
nodeA = f[nodeA][k];
nodeB = f[nodeB][k];
}
}
return f[nodeA][0];
}

int getDistance(int nodeX, int nodeY) {
int lcaNode = findLCA(nodeX, nodeY);
return distance[nodeX] + distance[nodeY] - 2 * distance[lcaNode];
}

int main() {
scanf("%d%d", &totalNodes, &totalQueries);
logLevel = (int)(log(totalNodes) / log(2)) + 1;

for (int i = 1; i <= totalNodes; i++) {
adjHead[i] = 0;
depth[i] = 0;
}

for (int i = 1; i < totalNodes; i++) {
int from, to;
scanf("%d%d", &from, &to);
addEdge(from, to);
addEdge(to, from);
}

bfsQueue.push(1);
depth[1] = 1;
distance[1] = 0;

while (!bfsQueue.empty()) {
int currentNode = bfsQueue.front();
bfsQueue.pop();

for (int i = adjHead[currentNode]; i; i = adjNext[i]) {
int neighborNode = adjVer[i];
if (depth[neighborNode]) {
continue;
}
depth[neighborNode] = depth[currentNode] + 1;
distance[neighborNode] = distance[currentNode] + 1;
f[neighborNode][0] = currentNode;
for (int k = 1; k <= logLevel; k++) {
f[neighborNode][k] = f[f[neighborNode][k-1]][k-1];
}
bfsQueue.push(neighborNode);
}
}

for (int i = 1; i <= totalQueries; i++) {
int path1Start, path1End, path2Start, path2End;
scanf("%d%d%d%d", &path1Start, &path1End, &path2Start, &path2End);

int distPath1 = getDistance(path1Start, path1End);
int distPath2 = getDistance(path2Start, path2End);
int crossDist1 = getDistance(path1Start, path2Start);
int crossDist2 = getDistance(path1End, path2End);

if (distPath1 + distPath2 >= crossDist1 + crossDist2) {
printf("Y\n");
} else {
printf("N\n");
}
}

return 0;
}