New update is available. Click here to update.

Tree Queries

PROBLEM STATEMENT

You are given a tree with 'N' vertices, where each vertex has an assigned integer. You are given 'Q' queries where each query can be of two types:

1 'U' 'V': Reverse the order of all the integers on the path between 'U' and 'V'.
2 'U' 'V': Print the sum of all the integers on the path between 'U' and 'V'.

More details on tree data structure: link

Input Format:

The first line contains two space-separated integers, ‘N’ and ‘Q’, denoting the number of vertices of the tree and the number of queries.

The next N-1 lines will contain two space-separated integers u and v, denoting an undirected edge between city u and city v.

The next line contains ‘N’ space-separated integers denoting the value associated with each node.

The next q lines contain three space-separated integers representing the queries of both types.

Output Format:

Output for each query of type two only, whether the path between the two cities of that query is alternating or not.

Output for each query will be printed in a separate line.

Note

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints:

1 <= N,Q <= 10^4
1 <= u,v <= N
1 <= value[i] <= 10^4

Where value[i] represents the value associated with the node.

Time Limit: 1 sec.

Approach 1

We will use heavy-light decomposition to solve this problem. The idea of this algorithm is that we will try to break the given tree into some segments where we can apply the segment tree to process each query in logarithmic time.

Algorithm:

update function:
- It takes a node as an argument and updates the size and the sum of the node.
propagate function:
- It is a recursive function that takes a node as an argument and reverses the order of the values in the subtree.
merge function:
- It merges the left subtree and right subtree into the root node.
split function:
- It splits a node into the child nodes and updates the information of the current node.
dfs function:
- It traverses the tree and calculates the depth, parent, and subtree size of each node.
hld function:
- It breaks the tree into different segments(chains) and calculates the chain number and head of the chain for each node.
lca function:
- It takes two nodes as an argument and returns the lower node among them when they are lifted and comes in the same chain.
getLastChainInd function:
- It takes two nodes as an argument and returns the index of the chain, which contains both the node when lifted upward.
queryUp function:
- It takes two nodes as an argument and returns the sum of all the values on the path between them.
queryPath:
- It returns the sum of all the values on the path between two nodes with the help of the queryUp function.
splitUp function:
- It splits the path between two given nodes and reverses the path between them.
mergeUp function:
- It merges the path between two given nodes, maintaining the order of the path.
reversePath function:
- It takes two nodes as an argument and reverses the order of the values on the path between them.
given function:
- Represent the tree in adjacency array.
- Call the above functions for pre-processing.
- Iterate over all the queries.
  - If it is of the first type, reverse the order of the path.
  - Else calculate the sum of all the values on the path between the two nodes.