Mojtaba has two trees, each of them has $$n$$ vertices. Arpa has $$q$$ queries, each in type $$v, u, x, y$$. Let $$s$$ be the set of vertices in the path from $$v$$ to $$u$$ in the first tree and $$p$$ be the set of vertices in the path from $$x$$ to $$y$$ in the second tree. Mojtaba has to calculate the size of $$s \cap p$$ for each query. Help him!
Input Format
The first line of input will contain two integers, $$n, q$$ ($$1 \le n, q \le 3 \cdot 10^5$$).
The next $$n-1$$ lines will contain edges of the first tree.
The next $$n-1$$ lines will contain edges of the second tree.
The next $$q$$ lines contain queries.
Output Format
For each query, let $$s$$ be the set of vertices in the path from $$v$$ to $$u$$ in the first tree and $$p$$ be the set of vertices in the path from $$x$$ to $$y$$ in the second tree, print the size of $$s \cap p$$ for each query.
5 5 3 4 5 1 4 1 3 2 1 2 4 1 5 1 2 3 4 1 5 5 3 4 2 4 4 3 1 3 1 5 5 3 5 2 1 3
0 1 1 2 3
The tree on the left is the first tree and the one in right is the second tree.
In the first query, \(s = \{4, 1\}, p = \{5\}\), so the size of \(s \cap p\) is 0.
In the third query, \(s = \{1, 2, 3, 4, 5\}, p = \{1, 2, 3\}\), so the answer is 3.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor