{"raw_statement":[{"iden":"statement","content":"You are given a directed tree with N with nodes numbered 1 to N and rooted at node 1. Each node initially contains 0 coins.\n\nYou have to handle a total of M operations: \n\nFirst line contains N and M. Each of the next N - 1 lines contains u and v denoting directed edge from node numbered u to v. \n\nEach of the next M lines contain queries of either Type 1 or 2.\n\nFor each query of Type 2, print the required sum.\n\n*Constraints* \n\nIn first update nodes 2 and 3 are increased by 2 coins each. \n\nIn second update nodes 4 and 5 are increased by 3 each. \n\n"},{"iden":"input","content":"First line contains N and M. Each of the next N - 1 lines contains u and v denoting directed edge from node numbered u to v. Each of the next M lines contain queries of either Type 1 or 2."},{"iden":"output","content":"For each query of Type 2, print the required sum.*Constraints*   1 ≤ N ≤ 105  1 ≤ M ≤ 104  0 ≤ L ≤ Maximum height of tree  0 ≤ Y ≤ 109  1 ≤ X, u, v ≤ N "},{"iden":"examples","content":"Input5 41 21 33 43 51 1 21 2 32 32 1Output810"},{"iden":"note","content":"In first update nodes 2 and 3 are increased by 2 coins each. In second update nodes 4 and 5 are increased by 3 each. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $.  \nLet $ T = (V, E) $ be a directed tree with $ V = \\{1, 2, \\dots, N\\} $, rooted at node 1, and $ |E| = N - 1 $.  \nLet $ c : V \\to \\mathbb{Z}_{\\geq 0} $ be the coin count function, initialized as $ c(i) = 0 $ for all $ i \\in V $.  \n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 10^5 $  \n2. Each edge is given as $ (u, v) \\in E $, denoting a directed edge from $ u $ to $ v $.  \n3. Queries are of two types:  \n   - **Type 1**: Given $ x $ and $ val $, increment $ c(y) $ by $ val $ for every node $ y $ in the subtree rooted at $ x $.  \n   - **Type 2**: Given $ x $, output $ \\sum_{y \\in \\text{subtree}(x)} c(y) $.  \n\n**Objective**  \nFor each Type 2 query with parameter $ x $, compute and output:  \n$$\n\\sum_{y \\in \\text{subtree}(x)} c(y)\n$$","simple_statement":"You are given a tree with N nodes (rooted at 1) and M operations.  \nInitially, all nodes have 0 coins.  \n\nThere are two types of operations:  \n- Type 1: Add coins to all nodes in the subtree of a given node.  \n- Type 2: Query the total coins in the subtree of a given node.  \n\nPrint the result for each Type 2 query.","has_page_source":false}