happy

”Happy” is a popular restaurant chain in Bulgaria. Maria traveled from Burgas to the nearby city of Varna – the birthplace of ”Happy”. She met her friends and went to one of the restaurants to celebrate her recent success at IATI. Known for its excellent service, the waitress gave Maria a challenge – if she solves it, the order will be free.

There are $N$ Happy restaurants in Varna, numbered from $0$ to $N-1$. They are connected by $N-1$ two-way paths, where each path has a happy energy value. Given two restaurants $x$ and $y$, we define a simple route between them as a sequence of paths starting from $x$ and ending in $y$ without repeating restaurants. The restaurants are connected in such a way so that there is exactly one simple route between each pair of restaurants.

For some unknown reason, the happiness of a simple route is defined as the bitwise XOR of the happy energies of the paths in it.

The challenge is that Maria has to find the sum of the happiness of the simple routes between each pair of open Happy restaurants. Initially, all restaurants are closed but we have $Q$ updates of two types:

• type 1 – given integers $l[j]$ and $r[j]$ such that $0 \leq l[j] \leq r[j] \leq N-1$, all restaurants with numbers in $[l[j], r[j]]$ become opened (if some restaurants are already opened, then they remain opened);
• type 2 – given integers $l[j]$ and $r[j]$ such that $0 \leq l[j] \leq r[j] \leq N-1$, all restaurants with numbers in $[l[j], r[j]]$ become closed (if some restaurants are already closed, then they remain closed);

Help Maria solve the challenge!

A bitwise XOR (^) is a binary operation on the binary representation of two numbers, applied bit by bit. It returns $1$ for each position if the corresponding bits are different, and $0$ if they are the same. For example, $4 \ 879$ ^ $4 \ 772 = 427$.

Implementation details

You should implement the function happy:

std::vector<long long int> happy (int N, int Q,
       std::vector<int> u, std::vector<int> v, std::vector<int> h,
       std::vector<int> t, std::vector<int> l, std::vector<int> r)

• $N$: the number Happy restaurants;
• $Q$: the number of updates;
• $u, v$ and $h$: vectors of $N-1$ integers, representing the restaurants and happy energies for the paths;
• $t, l, r$: vectors of $Q$ integers, representing the types and intervals for the updates.

This function will be called once for each test and has to return a vector with $Q$ numbers - the sum of the happiness of the simple routes between each pair of open restaurants after each update.

Restrictions

• $1 \leq N \leq 300 \ 000$
• $1 \leq Q \leq 300 \ 000$
• $1 \leq h[i] < 2^{20}$ for each $0 \leq i < N-1$
• There is exactly one simple route between each pair of restaurants.

Example 1

Consider the following call and illustration for the restaurants, for $N=6$ and $Q=5$:

happy(6, 5, {0, 1, 2, 2, 4}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 2},
       {1, 1, 2, 2, 1}, {1, 2, 2, 4, 0}, {2, 3, 2, 5, 5})

The $5$ updates are the following:

• $1 \ 1 \ 2$ (restaurants $1$ and $2$ become opened) – after the update we have only the simple route $1 \xleftrightarrow{2} 2$ with happiness $2$. Sum is $2$;
• $1 \ 2 \ 3$ (restaurants $2$ and $3$ become opened) – after the update we have the simple routes between restaurants $1$ and $2 \ (1 \xleftrightarrow{2} 2)$, $1$ and $3 \ (1 \xleftrightarrow{2} 2 \xleftrightarrow{2} 3)$, and $2$ and $3 \ (2 \xleftrightarrow{3} 3)$ with corresponding happiness $2, 2$ ^ $3 = 1$ and $3$ (^ is the C++ operator for bitwise XOR). Sum is $2 + 1 + 3 = 6$;
• $2 \ 2 \ 2$ (restaurant $2$ becomes closed) – after the update we have the simple route between restaurants $1$ and $3$. Sum is $1$;
• $2 \ 4 \ 5$ (restaurants $4$ and $5$ become closed) – after the update we have the simple route between restaurants $1$ and $3$. Sum is $1$;
• $1 \ 0 \ 5$ (restaurants $0$ to $5$ become opened) – after the update we have the simple routes between all pairs of restaurants. Sum is $56$.

Therefore, the call should return {2, 6, 1, 1, 56}.

Sample grader

The input format is the following:

• line $1$: two integers – the values of $N$ and $Q$.
• line $2+i$ to $2+N-2$: three integers $u[i], v[i], h[i]$ – representing a path between restaurants with numbers $u[i]$ and $v[i]$ with happy energy $h[i]$.
• line $N+1+j$ to $N+1+Q-1$: three integers $t[j],l[j],r[j]$ – representing an update of type $t[j]$ for an interval of restaurants with numbers from $l[j]$ and $r[j]$.

The output format is the following:

• line $i$: the $i$-th value as returned by the call.