題目描述

小倉鼠的和他的基（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;
}