Queries on tree 2 - MarisaOJ: Marisa Online Judge

Given a tree with

n

$n$ vertices and rooted at

1

$1$ . Each vertex has an initial value, and initially, all these values are

0

$0$ . There are

q

$q$ queries of two types: -

1 u

$1 u$ : Find the sum of values of vertices in the subtree rooted at

u

$u$ . -

2 u

$2 u$ : Find the value at vertex

u

$u$ . -

3 u v x

$3 u v x$ : Increase the values of vertices on the simple path from

u

$u$ to

v

$v$ by

x

$x$ . Answer the queries of types

1

$1$ and

2

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

n

$n$ and

q

$q$ . - The next

n - 1

$n - 1$ lines each contain two integers

u

$u$ and

v

$v$ , indicating an edge between

u

$u$ and

v

$v$ . - The next

q

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

1

$1$ and

2

$2$ . ### Constraints -

1 \leq n, q \leq 2 \times 10^{5}

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

1 \leq u, v \leq n

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

0 \leq | x | \leq 10^{6}

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

51012232425324225151215112234442312

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

Output:

00404208

$0 0 4 0 4 2 0 8$

Topic

Tree

Data structure

Rating

1900

Solution (0)

Solution