← 返回题目列表

Codeforces · 444/E

E. DZY 爱种植

中文机器翻译题面 查看原题

DZY 热爱种植,他喜欢解决树木问题。

DZY 有一个包含 n 个节点(编号从 1 到 n)的加权树(无环的连通无向图)。他将函数 g(x, y) (1 ≤ x, y ≤ n) 定义为节点 x 和 y 之间最短路径中的最长边。特别是对于每个 z,g(z, z) = 0。

对于每个整数序列 p1, p2, ..., pn (1 ≤ pi ≤ n),DZY 将 f(p) 定义为 $$\min_{i=1}^{n} g(i,p_i)$$。

DZY 想要找到这样一个序列 p,使得 f(p) 具有最大可能值。但还有一个限制:元素 j 最多只能在 p 中出现 xj 次。

请找出在所描述的限制下可能的最大 f(p)。

输入

第一行包含一个整数 n (1 ≤ n ≤ 3000)。

接下来的 n - 1 行中的每一行都包含三个整数 ai, bi, ci (1 ≤ ai, bi ≤ n; 1 ≤ ci ≤ 10000),表示 ai 和 bi 之间长度为 ci 的边。保证这些边形成一棵树。

接下来的 n 行中的每一行都描述序列 x 的一个元素。第 j 行包含整数 xj (1 ≤ xj ≤ n)。

输出

打印代表答案的单个整数。

示例

输入 #1

4
1 2 1
2 3 2
3 4 3
1
1
1
1

输出 #1

2

输入 #2

4
1 2 1
2 3 2
3 4 3
4
4
4
4

输出 #2

3

注意

在第一个样本中,最佳 p 之一是 [4, 3, 2, 1]。