#P18421. Bus Lines
Bus Lines
Bus Lines
Byteopolis 市有 个公交站,编号为 。站点之间由 条双向道路连接,任意两个站点都能只通过这些道路相互到达。因此,站点与道路构成一棵树。
市内运营着 条公交线路。第 条线路的公交车沿站点 与 之间的最短路径不断往返。你可以在其经过的任意站点上车或下车,包括两个终点站。线路的规划保证:任意两个站点之间都能仅乘坐公交到达,不需要以其它方式沿道路移动任何距离。
对 ,令 为从站点 到站点 所需乘坐的最少公交线路数。特别地,,且 。
请对每个站点 ,计算
原题补充:这些公交车采用太阳能、智能运行且不需要司机,因此始终在指定线路上往返行驶。
输入格式
第一行包含整数 ()。
接下来 行,每行包含两个整数 (),表示这两个站点之间有一条双向道路。保证这些道路构成一棵树。
下一行包含整数 ()。
接下来 行,每行包含两个整数 (,),表示一条在这两个站点之间的唯一树路径上往返的公交线路。保证任意两个站点之间都能仅乘公交到达。
输出格式
在一行中输出 个整数。其中第 个整数为 ,顺序与原站点编号一致。
完整原样例
输入:
6
1 2
5 4
6 5
3 1
1 5
3
6 1
2 3
6 4
输出:
6 9 9 10 7 7
原样例说明
样例中的站点和道路如下(原题配图):

从站点 2 到站点 4,可以先乘第二条线路(2 到 3)并在站点 1 下车,再乘第一条线路(6 到 1)并在站点 5 下车,最后乘第三条线路到站点 4。不可能只用两条线路完成,因此 。
原题给出了全部 的表格。第 行、第 列对应 ,每一行的和就是输出的相应整数:
