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