MoEngage has given you two trees $T_1$ and $T_2$. Both trees have $N$ nodes and are rooted at node $1$.
Definitions:
- $LCA_1(u,v) = $ Lowest common ancestor of node $u$ and node $v$ in tree $T_1$.
- $LCA_2(u,v) = $ Lowest common ancestor of node $u$ and node $v$ in tree $T_2$.
- $H_1(v) = $ Number of nodes in the shortest path from node $1$ to node $v$ in tree $T_1$. Note that, $H_1(1) = 1$.
- $H_2(v) = $ Number of nodes in the shortest path from node $1$ to node $v$ in tree $T_2$. Note that, $H_2(1) = 1$.
Find the maximum value of $H_1(LCA_1(u,v)) + H_2(LCA_2(u,v))$ over all pairs $(u,v)$ such that $u \neq v$.
More formally, find $\max\limits_{1 \leq u \lt v \leq N} [H_1(LCA_1(u,v)) + H_2(LCA_2(u,v))]$.
Input Format
- First line will contain $T$, the number of test cases. Then the test cases follow.
- First line of each test case contains a single integer $N$, the number of nodes.
- Each of the next $(N - 1)$ lines contain two integers $u$ and $v$ denoting an edge between nodes $u$ and $v$ in tree $T_1$.
- Each of the next $(N - 1)$ lines contain two integers $u$ and $v$ denoting an edge between nodes $u$ and $v$ in tree $T_2$.
Output Format
For each test case, output in a single line $\max\limits_{1 \leq u \lt v \leq N} [H_1(LCA_1(u,v)) + H_2(LCA_2(u,v))]$.
Constraints
- $1 \leq T \leq 10^4$
- $2 \leq N \leq 10^5$
- Sum of $N$ over all test cases does not exceed $10^5$.
Sample Input 1
2
6
2 1
3 1
4 3
5 3
6 1
2 1
3 2
4 1
5 3
6 1
4
2 1
3 2
4 2
2 1
3 1
4 1
Sample Output 1
5
3
Explanation
- Test case $1$: The trees $T_1$ and $T_2$ are:
For $u = 3$ and $v=5$, $LCA_1(3,5) = 3$, $LCA_2(3,5) = 3$, $H_1(3) = 2,H_2(3) = 3$. Thus, $H_1(LCA_1(3,5)) + H_2(LCA_2(3,5)) = H_1(3) + H_2(3) = 5$.
It can be proven that $5$ is the maximum possible answer for this case amongst all pairs $(u,v)$.
- Test case $2$: The trees $T_1$ and $T_2$ are:
For $u = 2$ and $v=4$, $LCA_1(2,4) = 2$, $LCA_2(2,4) = 1$, $H_1(2) = 2,H_2(1) = 1$. Thus, $H_1(LCA_1(2,4)) + H_2(LCA_2(2,4)) = H_1(2) + H_2(1) = 3$.
It can be proven that $3$ is the maximum possible answer for this case amongst all pairs $(u,v)$.
No comments:
Post a Comment