#P18421. Bus Lines

Bus Lines

Bus Lines

Byteopolis 市有 nn 个公交站,编号为 1,2,…,n1,2,\ldots,n。站点之间由 n−1n-1 条双向道路连接,任意两个站点都能只通过这些道路相互到达。因此,站点与道路构成一棵树。

市内运营着 mm 条公交线路。第 ii 条线路的公交车沿站点 cic_i 与 did_i 之间的最短路径不断往返。你可以在其经过的任意站点上车或下车,包括两个终点站。线路的规划保证:任意两个站点之间都能仅乘坐公交到达,不需要以其它方式沿道路移动任何距离。

对 1≤i,j≤n1\le i,j\le n,令 f(i,j)f(i,j) 为从站点 ii 到站点 jj 所需乘坐的最少公交线路数。特别地,f(i,i)=0f(i,i)=0,且 f(i,j)=f(j,i)f(i,j)=f(j,i)。

请对每个站点 ii,计算

∑j=1nf(i,j).\sum_{j=1}^{n}f(i,j).

原题补充:这些公交车采用太阳能、智能运行且不需要司机,因此始终在指定线路上往返行驶。

输入格式

第一行包含整数 nn(2≤n≤200 0002\le n\le200\,000)。

接下来 n−1n-1 行,每行包含两个整数 ai,bia_i,b_i(1≤ai,bi≤n1\le a_i,b_i\le n),表示这两个站点之间有一条双向道路。保证这些道路构成一棵树。

下一行包含整数 mm(1≤m≤200 0001\le m\le200\,000)。

接下来 mm 行,每行包含两个整数 ci,dic_i,d_i(1≤ci,di≤n1\le c_i,d_i\le n,ci≠dic_i\ne d_i),表示一条在这两个站点之间的唯一树路径上往返的公交线路。保证任意两个站点之间都能仅乘公交到达。

输出格式

在一行中输出 nn 个整数。其中第 ii 个整数为 ∑j=1nf(i,j)\sum_{j=1}^{n}f(i,j),顺序与原站点编号一致。

完整原样例

输入:

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。不可能只用两条线路完成,因此 f(2,4)=3f(2,4)=3。

原题给出了全部 f(i,j)f(i,j) 的表格。第 ii 行、第 jj 列对应 f(i,j)f(i,j),每一行的和就是输出的相应整数:

原题完整公交距离表