Company: google_26july
Difficulty: medium
Swap subtree Problem Description You are given an undirected tree with N nodes rooted at node 1. Every node has a value A[i] assigned to it. You need to answer Q queries of the following type: UVX Choose the subtree with U as the root node and subtree with V as the root node and swap their positions i.e. detach both the subtrees and swap their positions. If node U is an ancestor of node V or node V is an ancestor of node U, above swapping, is not performed. Find the sum of node values present in the subtree rooted at node X. If the swap operation is performed, then redo this operation, that is swap the subtree with U as the root node and subtree with V as the root node. Task Determine the required answer for Q queries. Notes Assume 1-based indexing. A node u is said to be an ancestor of node v if node u lies on a simple path between root and node v. Redo means re-doing the operation performed. Examples Example 1: Input: N = 5, A = [4, 1, 4, 2, 3], edges = [[1, 2], (2, 3), (2, 4), (1, 5