题目描述

$\textit{Pang}$ 住在一棵有 $n$ 个节点的树上。节点编号为 $1,2,\ldots, n$，$\textit{Pang}$ 起初在节点 $1$。每个节点都有一个温度。从第 $1$ 天早晨开始，每天早晨每个节点的温度都会减少 $1$。第 $0$ 天温度不会减少。每天的下午，如果 $\textit{Pang}$ 当前所在的节点温度为正，且他要前往的相邻节点温度不小于 $0$，他可以移动到一个相邻节点。每天的晚上，如果当前节点的温度大于等于 $0$，$\textit{Pang}$ 可以施放魔法，使他所在节点的温度增加 $k$。

对于每一对相邻节点 $a$ 和 $b$，$\textit{Pang}$ 最多只能从 $a$ 走到 $b$ 一次（从 $b$ 到 $a$ 也最多一次）。他也可以选择不移动，留在当前节点。

$\textit{Pang}$ 想要在每个节点上恰好施放一次魔法。他还希望在出发前尽可能长时间地待在节点 $1$。已知第 $1$ 天早晨之前每个节点的温度，$\textit{Pang}$ 应该在第几天准备离开？如果他在第 $i$ 天准备离开，他可以在这一天施放魔法，并将在第 $i+1$ 天进行第一次移动。如果即使在第 $0$ 天准备离开也无法在每个节点上恰好施放一次魔法，输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $k$（$2\le n\le 100000, 0\le k\le 1000000000$）。

接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示节点 $x$ 和 $y$ 之间有一条边（$1\le x, y\le n$）。

第 $n+1$ 行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示第 $i$ 个节点在第 $1$ 天早晨之前的温度（$0\le a_i\le 1000000000$）。

保证输入是一棵树结构。

输出格式

如果无法在每个节点上恰好施放一次魔法，输出 $-1$。

否则，输出一个整数 $x$，表示他必须在第 $x$ 天从节点 $1$ 准备出发。第 $1$ 天是第 $0$ 天之后的一天，依此类推。

3 1
1 2
1 3
4 3 5

1

3 1
1 2
1 3
2 10 10

-1

提示

由 ChatGPT 4.1 翻译