New update is available. Click here to update.

Last Updated: 6 Jul, 2021

Difficulty: Ninja

```
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'.
```

```
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 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.
```

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

```
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.
```

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.

SIMILAR PROBLEMS

Blueprint

Posted: 8 Sep, 2022

Difficulty: Moderate

Plantation

Posted: 9 Sep, 2022

Difficulty: Moderate

Capturing Grid

Posted: 14 Sep, 2022

Difficulty: Moderate

Rotting Oranges

Posted: 15 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: