Li Hua 有一个由 $$$n$$$ 个顶点和 $$$n-1$$$ 个边组成的树。顶点编号从 $$$1$$$ 到 $$$n$$$。
如果以下两个陈述之一为真,则一对顶点 $$$(u,v)$$$ ($$$u < v$$$) 被认为是可爱的:
- $$$u$$$ 是路径 $$$(u,v)$$$ 上所有顶点中索引最小的顶点。
- $$$v$$$ 是路径 $$$(u,v)$$$ 上所有顶点中索引最大的顶点。
将有 $$$m$$$ 次操作。在每次操作中,他决定一个整数$$$k_j$$$,然后将编号为$$$n+j$$$的顶点插入到树中,并与编号为$$$k_j$$$的顶点连接。
他想计算手术前和每次手术后可爱对的数量。
假设你是李华,请解决这个问题。
输入
第一行包含单个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的顶点数。
接下来的 $$$n-1$$$ 行包含树的边缘。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$; $$$u_i\ne v_i$$$) — 相应的边。给定的边形成一棵树。
下一行包含单个整数 $$$m$$$ ($$$1\le m\le 2\cdot 10^5$$$) — 操作数。
接下来的 $$$m$$$ 行包含操作 - 每行一个操作。第 $$$j$$$ 操作包含一个整数 $$$k_j$$$ ($$$1\le k_j < n+j$$$) — 一个顶点。
输出
打印 $$$m+1$$$ 整数 — 操作之前和每次操作之后可爱对的数量。
示例
输入 #1
7 2 1 1 3 1 4 4 6 4 7 6 5 2 5 6
输出 #1
11 15 19
注意
初始树如下图所示:
有 $$$11$$$ 可爱对 — $$$(1,5),(2,3),(2,4),(2,6),(2,7),(3,4),(3,6),(3,7),(4,5),(5,7),(6,7)$$$。
同样,我们可以在每次操作后计算可爱的对,结果是$$$15$$$和$$$19$$$。