[PA 2022] Miny

Luogu

IDLGP9260

Time9000ms

Memory1024MB

DifficultyP7

点分治2022拓扑排序强连通分量Tarjan分块线段树合并PA（波兰）bitset

**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Miny](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/min/)** 给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗地雷不超过其爆炸半径的地雷都会爆炸。我们定义两个点之间的距离是这两个点之间简单路径上边的长度和。对于每颗地雷，如果手动引爆它，确定有多少地雷会爆炸。注意对于每颗地雷，我们认为手动引爆它与手动引爆其他地雷互相独立。 ## Input 第一行包含一个整数 $n$，表示树的节点数（也是地雷个数）。树节点编号是从 $1$ 到 $n$ 的整数。第二行 $n$ 个整数 $r_1,r_2,\ldots,r_n$，第 $i$ 个整数为位于节点 $i$ 的地雷的爆炸半径。接下来 $n-1$ 行，每行三个整数 $a_i,b_i,c_i$，表示一条长 $c_i$ 的边连接节点 $a_i$ 和 $b_i$。保证输入可以正确表示一棵树。 ## Output 对于 $100\%$ 的数据，满足：输出一行 $n$ 个整数，第 $i$ 个整数表示如果我们手动引爆在节点 $i$ 上的地雷，有多少地雷会爆炸。 [samples] ## Note $1\le n\le 10 ^ 5, 0\le r_i\le 10^{18}, 1\le a_i,b_i\le n,1\le c_i\le 10^{12}$

Samples

Input #1

Output #1

4 1 1 4 2

API Response (JSON)

{
  "problem": {
    "name": "[PA 2022] Miny",
    "description": {
      "content": "**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Miny](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/min/)** 给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 9000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9260"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 4 [Miny](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/min/)**\n\n给定一棵树（无向无环图），树上每条边有一个确定的长度。每个点上都有一颗地雷，每个地雷有一个确定的爆炸半径。如果一个地雷爆炸了，所有距离这颗...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments