The problem statement is simple. You are given a rooted tree ( is the root) and every node has a cost, say . You have to perform operations. Each operation can be one of the following types.
Xinversion is almost similar to the inversion of an array. Xinversion of a node is the number of nodes inside the subtree of such that .
In the first line you are given two integers () and () , the number of nodes and the number of operations respectively.
The next line will contain integers, integer represents ().
Each of the next lines will contain two integers which means and are connected with an edge.
Each of the next lines will contain one of the two types of operations:
For every operations of type 2, print the Xinversion of . For more clear idea, see the sample input-output section.
5 5 1 2 3 4 5 1 2 2 3 2 4 3 5 2 1 2 2 1 3 1 1 4 1 2 1
4 3 2
Login to submit
First find the euler path of the tree and then the rest of the problem is fairly easy. You can use a...