NC238015. 抓人游戏

描述

输入描述

第一行输入两个整数分别代表  。
第二行输入  个用空格分割的整数分别代表  和  。
第三行输入  个用空格分割的整数分别代表  和  。
接下来输入  行，每行两个整数  代表编号为  和编号为  的结点之间存在一条边。
保证：
输入数据是一棵树
 

输出描述

输出共一行  个整数分别代表第  只虫子被抓住的时刻（游戏开始时是第  时刻）。

示例1

输入:

9 6
3 3 4 6 6 2 3
9 0 0 2 3 100 0
1 2
2 3
3 4
2 6
6 5
6 7
1 8
8 9

输出:

0 0 1 5 10 13

说明:

一种可能的最优解是：
机器人在编号为 3 的结点处先后抓住了虫子 1 和 虫子 2。（花费了 0 步）
机器人在编号为 4 的结点处抓住了虫子 3。（花费了 1 步）
机器人在编号为 5 的结点处抓住了虫子 4。（花费了 4 步）
机器人在编号为 9 的结点处抓住了虫子 5。（花费了 5 步）
机器人在编号为 2 的结点处抓住了虫子 6。（花费了 3 步）

原站题解