Mojtabas Trees and Arpas Queries <March HourStorm>

★★★★★

3.7

3 votes

Advanced Data Structures, Data Structures, Fenwick tree, Medium

Details

Submissions

Discussion

Editorial

Problem

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.

Sample Input

Sample Output

Time Limit: 5

Memory Limit: 256

Source Limit:

Explanation

First Tree. second tree

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.

Contributers:

Amirreza Poorakhavan