题目类型说明

这是一道提交函数题。你需要实现指定函数，不需要编写 main 函数，也不能从标准输入读取或向标准输出写入。

你需要实现：

std::vector<int> solve(
    int N,
    const std::vector<int>& teleportStrength,
    const std::vector<std::pair<int, int>>& edges
);

题目描述

今天是 Matthew 成为国家 Mauritania 光荣公民的第 10 年。

Mauritania 由 $N$ 个城市组成，城市编号为 $0, 1, \dots, N-1$。这些城市之间通过 $N-1$ 条道路连接。如果把城市看作点、道路看作边，那么整张图是一棵树。

Matthew 当前位于编号为 $0$ 的城市。他想知道：到达每一个城市所需的最短时间是多少。

Mauritania 是一个现代化国家，因此出行方式依赖于传送门。每个城市 $i$ 都有一个传送门，其力量为 $\text{teleportStrength}_i$。当 Matthew 位于城市 $i$ 时，他可以使用这里的传送门，传送到树上与 $i$ 的距离恰好为

条边的任意城市。每进行一次这样的传送，耗时恰好 $1$ 分钟。

对于每个城市 $v$（$0 \le v \le N-1$），请计算 Matthew 从城市 $0$ 出发到达 $v$ 所需的最短时间；如果无法到达，则输出 $-1$。

实现细节

你需要实现函数：

std::vector<int> solve(
    int N,
    const std::vector<int>& teleportStrength,
    const std::vector<std::pair<int, int>>& edges
);

其中：

• $N$：城市数
• $\text{teleportStrength}[i]$：城市 $i$ 的传送门力量
• edges：长度为 $N-1$ 的边集，表示树上的道路

你需要返回一个长度为 $N$ 的数组 dist，其中：

• dist[i] 表示从城市 $0$ 到城市 $i$ 的最短时间
• 若城市 $i$ 不可达，则 dist[i] = -1

你的程序：

• 不得包含 main 函数
• 可以自行定义辅助函数、类、全局变量等
• 不得读写标准输入输出

本地测试

题目提供本地 grader：Lgrader.cpp，以及头文件 teleport.h。

你应将自己的代码与本地 grader 一同编译，例如：

g++ -O2 -std=c++17 -Wall teleport.cpp Lgrader.cpp -o teleport.exe

数据范围

• $2 \le N \le 5 \times 10^5$
• $1 \le \text{teleportStrength}_i \le 10^9$

子任务

样例

输入

5
1 1 2 2 7
0 1
0 2
2 3
3 4

输出

0 1 1 -1 2

样例解释

因为 Matthew 一开始就在城市 $0$，所以到达城市 $0$ 需要 $0$ 分钟。

使用城市 $0$ 的传送门（力量为 $1$），他可以在 $1$ 分钟内到达城市 $1$ 和 $2$。

继续依次使用城市 $0$ 和城市 $2$ 的传送门，他可以在 $2$ 分钟内到达城市 $4$。

可以证明，城市 $3$ 无法到达，因此答案为 $-1$。