Logu p3398 hamster looks for sugar (double LCA on the tree to judge whether the two paths in the tree intersect)

Hamsters look for sugar

Title Description

Hamster's and his base （mei） friend （zi）sugar Living in underground caves , The number of each node is 1~n. The underground cave is a tree structure . On this day, hamster plans to go from his bedroom （a） To the restaurant （b）, And his base friend is going to be in his bedroom at the same time （c） To the library （d）. They all take the shortest path . Now little hamster wants to know , Is it possible to be somewhere , You can meet his friends ？

Hamsters are so weak , And every day zzq Uncle abuse , Please come and save him ！

Input format

Two positive integers in the first line n and q, It indicates the number of nodes in the tree and the number of queries .

Next n-1 That's ok , Two positive integers per line u and v, Representation node u To the node v There is a side between .

Next q That's ok , Four positive integers per line a、b、c and d, Indicates the node number , That is, an inquiry , Its meaning is as above .

Output format

For each inquiry , If there is a public point , Output capital letters “Y”; Otherwise output “N”.

Examples #1

The sample input #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

Sample output #1

Y
N
Y
Y
Y

Tips

__ Time limit of this question 1s, Memory limit 128M, Because the speed of the new evaluation machine is close to NOIP The speed of the evaluation machine , Note the effect of the constant problem .__

20% The data of n<=200,q<=200

40% The data of n<=2000,q<=2000

70% The data of n<=50000,q<=50000

100% The data of n<=100000,q<=100000

The question ：

Given n Nodes , Nodes are connected in total n - 1 side , give most 1e5 A asked , Every inquiry is judged a ~ b and c ~ d Whether the two paths intersect . Intersection output ‘Y’, otherwise ‘N’.

Ideas ：

Draw more pictures to simulate , You can find the following magical rule ：

If a ~ b and c ~ d Two paths intersect , Then there must be a ~ b The path of LCA stay c ~ d On the path , perhaps c ~ d The path of LCA stay a ~ b On the path .

and Judge a node x, Whether in the path s - t The following conditions need to be met ：（ please remember , Important conclusions ）

depth[x] >= depth[lca(s, t)]	// x  be located  s、t  Two o'clock  lca  Same height or below  

lca(s, x) = x || lca(t, x) = x;	// s、x  Of  lca  yes  x  or  t、x  Of  lca  yes  x

Code ：

#define _CRT_SECURE_NO_WARNINGS 1
#include <bits/stdc++.h>

using namespace std;
//#define int long long
//#define map unordered_map
const int N = 1e5 + 10, M = N << 1;
int n, q;
int h[N], e[M], ne[M], idx;
int depth[N];
int fa[N][18];

void add(int a, int b)
{
    
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void bfs(int u)
{
    
	queue<int> q; q.push(u);
	while (q.size())
	{
    
		auto t = q.front(); q.pop();
		for (int i = h[t]; ~i; i = ne[i])
		{
    
			int j = e[i];
			if (depth[j] > depth[t] + 1)
			{
    
				depth[j] = depth[t] + 1;
				q.push(j);
				fa[j][0] = t;
				for (int k = 1; k <= 17; ++k)
				{
    
					fa[j][k] = fa[fa[j][k - 1]][k - 1];
				}
			}
		}
	}
}

int lca(int a, int b)
{
    
	if (depth[a] < depth[b]) swap(a, b);

	for (int k = 17; k >= 0; --k)
	{
    
		if (depth[fa[a][k]] >= depth[b]) a = fa[a][k];
	}

	if (a == b) return a;

	for (int k = 17; k >= 0; --k)
	{
    
		if (fa[a][k] != fa[b][k])
		{
    
			a = fa[a][k];
			b = fa[b][k];
		}
	}

	return fa[a][0];
}

void init(int root)
{
    
	memset(depth, 0x3f, sizeof depth);
	depth[0] = 0, depth[root] = 1;
	bfs(root);
}

bool jud(int a, int b, int c, int d)
{
    
	int p = lca(a, b);
	if (depth[p] >= depth[lca(c, d)] && (lca(c, p) == p || lca(d, p) == p))
		return true;
	return false;
}

signed main()
{
    
	int T = 1; //cin >> T;

	while (T--)
	{
    
		memset(h, -1, sizeof h);
		cin >> n >> q;
		int t = n - 1;
		int root = 0;
		for (int i = 0; i < t; ++i)
		{
    
			int u, v; scanf("%d%d", &u, &v);
			if (!i) root = u;
			add(u, v), add(v, u);
		}
		init(root);
		while (q--)
		{
    
			int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
			if (jud(a, b, c, d) || jud(c, d, a, b))
			{
    
				puts("Y");
			}
			else puts("N");
		}
	}

	return 0;
}