A. Queries on the Tree

Codeforces

IDCF10058A

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

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. You have to handle a total of M operations: 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. For each query of Type 2, print the required sum. *Constraints* 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. ## Input 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. ## Output 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 [samples] ## Note 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.

**Definitions** Let $ N, M \in \mathbb{Z}^+ $. Let $ T = (V, E) $ be a directed tree with $ V = \{1, 2, \dots, N\} $, rooted at node 1, and $ |E| = N - 1 $. Let $ c : V \to \mathbb{Z}_{\geq 0} $ be the coin count function, initialized as $ c(i) = 0 $ for all $ i \in V $. **Constraints** 1. $ 1 \leq N, M \leq 10^5 $ 2. Each edge is given as $ (u, v) \in E $, denoting a directed edge from $ u $ to $ v $. 3. Queries are of two types: - **Type 1**: Given $ x $ and $ val $, increment $ c(y) $ by $ val $ for every node $ y $ in the subtree rooted at $ x $. - **Type 2**: Given $ x $, output $ \sum_{y \in \text{subtree}(x)} c(y) $. **Objective** For each Type 2 query with parameter $ x $, compute and output: $$ \sum_{y \in \text{subtree}(x)} c(y) $$

API Response (JSON)

{
  "problem": {
    "name": "A. Queries on the Tree",
    "description": {
      "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. You have to handle a total of M operations:  First line contains N and M. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10058A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "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. ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**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} $...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments