BZOJ4372 烁烁的游戏

Luogu

IDLGP10603

Time3000ms

Memory512MB

DifficultyP6

线段树树状数组O2优化动态树分治

题目背景可以被抽象成这个问题：给一棵 $n$ 个结点的树，边权均为 $1$，初始点权均为 $0$。进行 $m$ 次操作： - $\text{Q x}$：询问结点 $x$ 的点权。 - $\text{M x d w}$：将树上与结点 $x$ 距离不超过 $d$ 的节点的点权均加上 $w$。 ## Input 第一行两个正整数 $n,m$。接下来的 $n-1$ 行，每行三个正整数 $u,v$，代表 $u,v$ 之间有一条边。接下来的 $m$ 行，每行给出上述两种操作中的一种。 ## Output 对于每个 $Q$ 操作，输出当前 $x$ 结点的点权。 [samples] ## Background 题目来自原 BZOJ，我们承认题面及原数据的版权均属于原 BZOJ 或将题目授权给 BZOJ 使用的出题人。如果您是版权所有者且认为我们侵犯了您的权益，可联系我们。 --- 烁烁很喜欢爬树，这吓坏了树上的皮皮鼠。给定一颗 $n$ 个节点的树，边权均为 $1$，初始树上没有皮皮鼠。烁烁他每次会跳到一个节点 $u$ ，把周围与他距离不超过 $d$ 的节点各吸引出 $w$ 只皮皮鼠。皮皮鼠会被烁烁吸引，所以会一直待在节点上不动。烁烁很好奇，在当前时刻，节点 $u$ 有多少个他的好朋友——皮皮鼠。 ## Note 对于所有数据，保证 $1\leq n,m\leq 10^5$，$|w|\leq 10^4$。注意：$w$ 不一定为正整数，

Samples

Input #1

Output #1

2
3
6

API Response (JSON)

{
  "problem": {
    "name": "BZOJ4372 烁烁的游戏",
    "description": {
      "content": "题目背景可以被抽象成这个问题： 给一棵 $n$ 个结点的树，边权均为 $1$，初始点权均为 $0$。进行 $m$ 次操作： - $\\text{Q x}$：询问结点 $x$ 的点权。 - $\\text{M x d w}$：将树上与结点 $x$ 距离不超过 $d$ 的节点的点权均加上 $w$。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10603"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "题目背景可以被抽象成这个问题：\n\n给一棵 $n$ 个结点的树，边权均为 $1$，初始点权均为 $0$。进行 $m$ 次操作：\n- $\\text{Q x}$：询问结点 $x$ 的点权。\n- $\\text{M x d w}$：将树上与结点 $x$ 距离不超过 $d$ 的节点的点权均加上 $w$。\n\n## Input\n\n第一行两个正整数 $n,m$。\n\n接下来的 $n-1$ 行，每行三个正整数 $u,v...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments