Queries on tree - MarisaOJ: Marisa Online Judge

Given a tree with

$n$ vertices rooted at

$1$ , where each vertex initially has a value of

$0$ . There are

$q$ queries, each belonging to one of the following two types: -

$1 u x$ : Increase the values of vertices in the subtree rooted at

$u$ by

$x$ . -

$2 u x$ : Increase the value of vertex

$u$ by

$x$ . -

$3 u v$ : Find the sum of values of vertices on the simple path from

$u$ to

$v$ . Answer the queries of type

$3$ . ### Input - The first line contains two integers

$n$ and

$q$ . - The next

$n-1$ lines each contain two integers

$u$ and

$v$ , indicating there is an edge between

$u$ and

$v$ . - The next

$q$ lines each contain a query in the specified format. ### Output - Print an integer, the answer for each query of type

$3$ . ### Constraints -

$1 \le n,q \le 2 \times 10^5$ . -

$1 \le u, v \le n$ . -

$0 \le |x| \le 10^6$ . ### Example Input:

$5 10 1 2 2 3 2 4 2 5 1 4 -1 2 5 -4 3 4 5 3 2 5 3 2 2 3 4 2 2 5 5 3 1 2 1 3 3 3 2 1$

Output:

$-5 -4 0 -1 0 0$

Topic

Tree

Data structure

Rating

1900

Solution (0)

Solution